跳到主要内容

4Sum

描述​

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:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a≤b≤c≤da \leq b \leq c \leq d)
  • 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)

分析​

先排序，然后双指针左右夹逼，复杂度 O(n3)O(n^3)，会超时。

可以用一个 hashmap 先缓存两个数的和，最终复杂度O(n3)O(n^3)。这个策略也适用于 3Sum 。

代码​

双指针​

# 4Sum
# 双指针
# Time Complexity: O(n^3)，Space Complexity: O(n)
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        return self.kSum(nums, 0, target, 4)

    def twoSumII(self, nums: List[int], start: int, target:int)->List[List[int]]:
        result = []
        low, high = start, len(nums)-1
        while low < high:
            sum = nums[low] + nums[high]
            if sum < target:
                low += 1
            elif sum > target:
                high -= 1
            else:
                result.append([nums[low], nums[high]])
                low += 1
                high -= 1
                while low < high and nums[low] == nums[low-1]:
                    low += 1
                while low < high and nums[high] == nums[high+1]:
                    high -= 1
        return result

    def kSum(self, nums: List[int], start: int, target: int, k: int) -> List[List[int]]:
        result = []
        if k == 2:
            return self.twoSumII(nums, start, target)
        if start + k > len(nums) or nums[start] * k > target or nums[-1] * k < target:
            return result
        for i in range(start, len(nums)):
            if i == start or nums[i] != nums[i-1]:
                for lst in self.kSum(nums, i+1, target-nums[i], k-1):
                    result.append([nums[i]] + lst)
        return result

HashSet​

其他代码完全一样，仅仅是twoSumII()不一样。

# 4Sum
# 先排序，然后twoSumII()用HashSet实现
# Time Complexity: O(n^3)，Space Complexity: O(n)
class Solution:
    def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
        nums.sort()
        return self.kSum(nums, 0, target, 4)

    def twoSumII(self, nums: List[int], start: int, target:int)->List[List[int]]:
        result = []
        s = set()
        for i in range(start, len(nums)):
            if len(result) == 0 or result[-1][1] != nums[i]:
                complement = target - nums[i]
                if complement in s:
                    result.append([complement, nums[i]])
            s.add(nums[i])
        return result

    def kSum(self, nums: List[int], start: int, target: int, k: int) -> List[List[int]]:
        result = []
        if k == 2:
            return self.twoSumII(nums, start, target)
        if start + k > len(nums) or nums[start] * k > target or nums[-1] * k < target:
            return result
        for i in range(start, len(nums)-k+1):
            if i == start or nums[i] != nums[i-1]:
                for lst in self.kSum(nums, i+1, target-nums[i], k-1):
                    result.append([nums[i]] + lst)
        return result

kSum 问题总结​

对于 kSum 这类问题，

  1. 如果求的是具体的位置，就不能 sort，因为排序后位置信息就丢失了
  2. 如果求位置，用 HashMap, 求组合本身，用 HashSet 就足够了
  3. 如果求的是组合本身且 k>2, 无论如何，先排序，然后再考虑用双指针或者 HashSet
  4. twoSumII()可以作为一个通用的底层函数，它往往有两种实现，双指针或者 HashSet(HashMap)
  5. twoSumII()的 HashSet 实现，比较直观的是两次遍历，可以优化成单次遍历。

2Sum求的是位置，因此不能 sort。用两轮循环暴力搜索，时间复杂度O(n2)O(n^2), 空间复杂度 O(1)；如果用一个 HashMap 来缓存位置，时间复杂度可以降低到 O(n)，代价是空间复杂度变为 O(n)。

2Sum II求的是组合本身，nums数组已排好序，因此就不必再排序了，直接用双指针左右夹逼，时间复杂度 O(n)，空间复杂度 O(1)；也可以用 HashSet，时间复杂度 O(n)，空间复杂度 O(n)，并没有比双指针快，却更占内存。因此这题最佳方法是双指针。

3Sum求的是组合本身且 k>2, 先排序，然后用双指针或者 HashSet 两种方法都可以。

4Sum求的是组合本身且 k>2, 先排序，然后用双指针或者 HashSet 两种方法都可以。

相关题目​