leetcode--18--四数之和

题目：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：

答案中不可以包含重复的四元组。

示例：

给定数组 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。

满足要求的四元组集合为：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

链接：https://leetcode-cn.com/problems/4sum

思路：
1、n数之和可以转换为n-1之和加上n位置值之和

Python代码：

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        #求n个数之和
        def nSum(l,t,n):     
            if n==2:
                return twosum(l,t)
            else:
                result=[]
                #print(l)
                for index,num in enumerate(l):                   
                    if num>0 and num>t:
                        break
                    if index-1>=0 and num==l[index-1]:
                        continue
                    else:
                        temp=nSum(l[index+1:],t-num,n-1)
                        for i in temp:
                            i.insert(0,num)
                        result+=temp 
                return result
            
        def twosum(l,t):
            i,j=0,len(l)-1
            result=[]

            while i<j:
                if l[i]>0 and l[i]>t:
                    break
                elif i-1>=0 and l[i]==l[i-1]:
                    i+=1
                elif l[i]+l[j]>t:
                    j-=1
                elif l[i]+l[j]<t:
                    i+=1
                else:
                    result.append([l[i],l[j]])
                    i+=1
                    j-=1
            #print(result)
            return result
                
        nums.sort()
        return nSum(nums,target,4)