18. 4 Sum

Leetcode

Given an array S of n integers, are there elements a, b, c, and d in S 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.

For example, given array S = [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]
]

思路其实非常简单，无非是把4Sum问题转化为3Sum问题。

class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """

        # 特殊情况，数字个数小于4
        n = len(nums)
        if n < 4:
            return []

        nums = sorted(nums)

        i = 0
        results = []
        while i < n-3:
            self.threesum(nums[i+1:], target-nums[i], nums[i], results)

            i += 1

            # repeat situation
            while (i<n-3) and (nums[i] == nums[i-1]):
                i += 1

        return results

    def threesum(self, nums, target, first,  results):
        i = 0
        n = len(nums)
        while i < n-2:
            left = i + 1
            right = n-1

            while left < right:
                val = nums[i] + nums[left] + nums[right]
                if val == target:
                    results.append([first, nums[i], nums[left], nums[right]])
                    print([first, nums[i], nums[left], nums[right]])
                    left += 1
                    right -= 1
                    # repeat situation
                    while (left< right) and (nums[left]==nums[left-1]):
                        left += 1
                    while (left<right) and (nums[right]==nums[right+1]):
                        right -= 1

                elif val < target:
                    left += 1
                else:
                    right -= 1

            i += 1
            # repeat situation
            while (i < n -2) and nums[i] == nums[i-1]:
                i += 1

        return None