18. 4Sum

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

The solution set must not contain duplicate quadruplets.

Example:

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

解题要点：

用3sum的方法来做，先遍历排好序的数组，然后调用3sum的函数，把当前数加到找好的3sum result前面即可。

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        def threeSum(nums, target):
            res = []
            for i in range(len(nums) - 2):
                l = i + 1
                h = len(nums) - 1
                if i > 0 and nums[i] == nums[i-1]:
                    continue 
                s = target - nums[i]           
                while l < h:                    
                    if nums[l] + nums[h] == s:
                        res.append([nums[i], nums[l], nums[h]])
                        while l < h and nums[l] == nums[l+1]: l += 1
                        while l < h and nums[h] == nums[h-1]: h -= 1
                        l += 1
                        h -= 1
                    elif nums[l] + nums[h] < s:
                        l += 1
                    else:
                        h -= 1
            return res
        
        result = []
        nums.sort()
        for j in range(len(nums) - 3):
            if j > 0 and nums[j] == nums[j-1]:
                continue
            temp = threeSum(nums[j+1:], target - nums[j])
            for n in temp:
                result.append([nums[j]] + n)
        return result