LeetCode 018 4Sum

LeetCode

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

0 <= a, b, c, d < n a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]

Constraints: 1 <= nums.length <= 200
-10<sup>9</sup> <= nums[i] <= 10<sup>9</sup> -10<sup>9</sup> <= target <= 10<sup>9</sup>

题目大意：

求四数和等于target。这些数值结果排序后不能重复。

解题思路：

类似于3sum，但需要更加一般化。用递归。不能用求所有笛卡尔积版的Two sum，会TLE。

解题步骤：

N/A

注意事项：

1. k_sum接口含k_sum(nums, target, k), 基础case为two_sum, 遍历nums每个元素，若重复跳过，将(子数组，target-nums[i], k-1)递归，返回结果拼接
2. two_sum也是遇到重复元素跳过，若等于target，要左右指针均移动

Python代码：

def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
	nums.sort()
	return self.k_sum(nums, target, 4)

def k_sum(self, nums, target, k):
	if k == 2:
		return self.two_sum(nums, target)
	# assume 3 sum
	res = []
	for i in range(len(nums)):
		if i >= 1 and nums[i - 1] == nums[i]: # remember
			continue
		sub_res = self.k_sum(nums[i + 1:], target - nums[i], k - 1)
		for li in sub_res:
			res.append([nums[i]] + li)
	return res

def two_sum(self, nums, target):
	i, j, res = 0, len(nums) - 1, []
	while i < j:
		if (i >= 1 and nums[i - 1] == nums[i]) or nums[i] + nums[j] < target:
			i += 1
		elif (j + 1 < len(nums) and nums[j] == nums[j + 1]) or nums[i] + nums[j] > target:
			j -= 1
		else:
			res.append([nums[i], nums[j]]) # remember to use list rather than tuple
			i += 1 # remember
			j -= 1
	return res

算法分析：

时间复杂度为O(n3)，空间复杂度O(1)