給定一個包含 n 個整數(shù)的數(shù)組 nums 和一個目標(biāo)值 target镜豹，判斷 nums 中是否存在四個元素 a份企，b，c 和 d 撇贺，使得 a + b + c + d 的值與 target 相等赌莺？找出所有滿足條件且不重復(fù)的四元組。

注意：答案中不可以包含重復(fù)的四元組松嘶。

示例：

給定數(shù)組 nums = [1, 0, -1, 0, -2, 2]艘狭，和 target = 0。

滿足要求的四元組集合為：
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

我的方法：

總的思路與3Sum()類似翠订，也是用循環(huán)+雙指針巢音，只不過這里使用的是雙重循環(huán)。同樣的尽超，在處理時應(yīng)該注意以下兩個方面：

1. 注意剔除重復(fù)項官撼。
2. 當(dāng)找到滿足條件的項目時，不要忘了移動k,l似谁，否則會進(jìn)入死循環(huán)歧寺。

執(zhí)行效率一般：執(zhí)行用時 : 860 ms, 在4Sum的Python提交中擊敗了20.70% 的用戶。內(nèi)存消耗 : 10.7 MB, 在4Sum的Python提交中擊敗了14.94% 的用戶棘脐。

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        leng=len(nums)# 數(shù)組長度
        ans=[]
        if len(nums)<4:
            return []
        # 雙重循環(huán)
        for i in range(leng-3):
            for j in range(i+1,leng-2):
                k=j+1
                l=leng-1
                # k,l移動的條件
                if i==0 or nums[i]!=nums[i-1]:
                    while k<l:
                        if nums[i]+nums[j]+nums[k]+nums[l]>target:
                            l-=1
                        elif nums[i]+nums[j]+nums[k]+nums[l]<target:
                            k+=1
                        else:
                            # 注意剔除重復(fù)項
                            if [nums[i],nums[j],nums[k],nums[l]] not in ans:
                                ans.append([nums[i],nums[j],nums[k],nums[l]])
                            # 不要忘了移動k,l
                            k+=1
                            l-=1
        return ans

別人的方法：
這套方法看起來有點(diǎn)意思斜筐，基本思想是用遞歸把NSum轉(zhuǎn)換為2Sum。還有其它有意思的點(diǎn)：

1. 直接用results記錄結(jié)果蛀缝，子函數(shù)findNsum()中的return并不實際返回值顷链，只是相當(dāng)于break的功能。
2. 依然是要先對nums排序屈梁，排序之后很多事情都好辦多了嗤练，比如：判斷什么情況下就不用再接著計算了。
3. findNsum函數(shù)中的nums表示數(shù)組在讶，target表示目標(biāo)值煞抬，N表示相加的數(shù)字個數(shù)，result表示results[0]构哺，results表示最終結(jié)果革答。

速度果然快了許多：執(zhí)行用時 : 124 ms, 在4Sum的Python提交中擊敗了84.18% 的用戶。內(nèi)存消耗 : 10.7 MB, 在4Sum的Python提交中擊敗了14.94% 的用戶曙强。但遞歸應(yīng)該不是速度更快的原因残拐，應(yīng)該是其中做了很多的跳過操作，節(jié)省了不少的時間碟嘴。

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """ 
        nums.sort()
        results = []
        self.findNsum(nums, target, 4, [], results)
        return results
    def findNsum(self, nums, target, N, result, results):
        if len(nums) < N or N < 2: return

        # solve 2-sum
        if N == 2:
            l,r = 0,len(nums)-1
            while l < r:
                if nums[l] + nums[r] == target:
                    results.append(result + [nums[l], nums[r]])
                    l += 1
                    r -= 1
                    # 去重的方式很獨(dú)特
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while r > l and nums[r] == nums[r + 1]:
                        r -= 1
                elif nums[l] + nums[r] < target:
                    l += 1
                else:
                    r -= 1
        else:
            for i in range(0, len(nums)-N+1):   # careful about range
                if target < nums[i]*N or target > nums[-1]*N:  # take advantages of sorted list
                    break
                if i == 0 or i > 0 and nums[i-1] != nums[i]:  # recursively reduce N
                    self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
        return