3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note: The solution set must not contain duplicate triplets.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is:
[[-1, 0, 1], [-1, -1, 2]]

class Solution(object):
    def threeSum(self, nums):
        res = []
        nums.sort()
        length = len(nums)
        for i in range(length-2): 
            if nums[i]>0: break
            if i>0 and nums[i]==nums[i-1]: continue 
            l, r = i+1, length-1
            while l<r:
                total = nums[i]+nums[l]+nums[r]
                if total<0:
                    l+=1
                elif total>0: 
                    r-=1
                else: 
                    res.append([nums[i], nums[l], nums[r]])
                    while l<r and nums[l]==nums[l+1]: 
                        l+=1
                    while l<r and nums[r]==nums[r-1]: 
                        r-=1
                    l+=1
                    r-=1
        return res

• continue那一句非常重要，防止出现两个duplicate的set，这样就不用在建立好之后再remove the duplicate。包括后面的判断l和r有没有重复的
• 后面的l-r部分就是两端逼近，只有细节不同。
• 和2sum一样，都要先排序。

Runtime: 680 ms, faster than 91.77% of Python3 online submissions for 3Sum.
Memory Usage: 16.1 MB, less than 100.00% of Python3 online submissions for 3Sum.

2. 4Sum
   看到discuss里有人给出了n-sum的解法...

class Solution:
    def fourSum(self, nums, target):
        def findNsum(nums, target, N, cur):
            if len(nums) < N or N < 2 or nums[0] * N > target or nums[-1] * N < target:  
                return            
            if N == 2:  # 2-sum problem
                l, r = 0, len(nums) - 1
                while l < r:
                    s = nums[l] + nums[r]
                    if s == target:
                        res.append(cur + [nums[l], nums[r]])
                        while l < r and nums[l] == nums[l - 1]:
                            l += 1
                        while l < r and nums[r] == nums[r - 1]:
                            r -= 1
                        l += 1
                        r -= 1
                    elif s < target:
                        l += 1
                    else:
                        r -= 1
            else:  # reduce to N-1 sum problem
                for i in range(len(nums) - N + 1):
                    if i == 0 or nums[i - 1] != nums[i]:
                        findNsum(nums[i + 1 :], target - nums[i], N - 1, cur + [nums[i]])

        res = []
        findNsum(sorted(nums), target, 4, [])
        return res

膜膜膜，我自己总是试图直接引用之前的3sum，但是总是会有重复不重复这类问题，除非到最后了统一去重，要不然这种分层的很难在每一层筛选一下。
核心部分还是2sum，但是中间cur那个部分还有判断需不需要停止循环，都考虑的很周到。