这类题都是2sum的变种。在2sum里，在排序的数列中使用双向指针。当2sum大于目标值，右指针减一；当2sum小于目标值，左指针加一。

3sum (题号15)

本题要注意对第一个和第二个元素去重：

class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:                def twosum(arr, start,  target):            left, right = start, len(nums)-1            while left < right:                cursum = arr[left] + arr[right]                 if cursum == target:                    results.append([-target, arr[left], arr[right]])                    left += 1                            right -= 1                    # avoid the duplicate of the second one                    while left<right and arr[left]==arr[left-1]:                        left += 1                elif cursum > target:                    right -= 1                elif cursum < target:                    left += 1                            nums.sort()                results = []        for i in range(len(nums)):            # avoid the duplicate of the first one            if i> 0 and nums[i]== nums[i-1]:                continue            twosum(nums, i+1, -nums[i])                    return results

Time complexity: O(); Space complexity: O() in the worst case of sorting algorithm.

在quick sort里，即使array操作都是in-place，但空间复杂度依赖递归的深度。

3sum closest (题号16)

用和上一题一样的模板。

class Solution:    def threeSumClosest(self, nums: List[int], target: int) -> int:                nums.sort()        N = len(nums)                # fix the first element find the closest result        def twosum(first):            second, third = first+1, N-1            mindiff = sys.maxsize            while second < third:                cursum = nums[first] + nums[second] + nums[third]                diff = cursum - target                if abs(diff) < mindiff:                     mindiff = abs(diff)                    res = diff                 if cursum > target:                    third -= 1                elif cursum < target:                    second += 1                else:                    return res            return res                mindiff = sys.maxsize        # iterate the first element through the array        for i in range(N-2):            diff = twosum(i)            if abs(diff) < mindiff:                mindiff = abs(diff)                res = diff                if res == 0: return target                return target + res

Time complexity: O(); Space complexity: O() in the worst case of sorting algorithm

3sum Smaller (题号259)

class Solution:    def threeSumSmaller(self, nums: List[int], target: int) -> int:                nums.sort()        N = len(nums)        if N < 3: return 0                # fix the first element find the closest result        def twosum(first):            second, third = first+1, N-1            res = 0            while second < third:                cursum = nums[first] + nums[second] + nums[third]                if cursum >= target:                    third -= 1                elif cursum < target:                    res += third - second                    second += 1            return res                res = 0        # iterate the first element through the array        for i in range(N-2):            res += twosum(i)                return res

Time complexity: O(); Space complexity: O() in the worst case of sorting algorithm.

4sum (题号18)

重点还是去重。

class Solution:    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:            N = len(nums)        if N < 4: return []        nums.sort()        res = []        def twosum(first, second):            third, fourth = second+1, N-1            while third < fourth:                curr = nums[first]+nums[second]+nums[third]+nums[fourth]                if curr == target:                    res.append([nums[first], nums[second], nums[third], nums[fourth]])                    third += 1                    fourth -= 1                    while third < N-1 and nums[third]== nums[third-1]:                        third += 1                elif curr < target:                    third += 1                else:                    fourth -= 1                    for first in range(N-3):            if first > 0 and nums[first] == nums[first-1]:                continue            for second in range(first+1, N-2):                if second > first + 1 and nums[second] == nums[second-1]:                    continue                twosum(first, second)                return res

Time complexity: O(); Space complexity: O() in the worst case of sorting algorithm.