18. 4Sum
Category: /leetcodeGiven 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
-109 <= nums[i] <= 109
-109 <= target <= 109
Solution:
- Two pointers: this solution works for n-sum. The idea is to have
n==2as a base, for larger case, recusively calls(n-1)Sum.
# generalize it to any target
def fourSum(nums, target):
nums.sort()
return nSum(nums, 4, 0, 0)
def nSum(nums, n, start, target):
sz = len(nums)
res = []
if n < 2 or sz < n: return res
# 2sum is the base
if n == 2:
lo, hi = start, sz - 1
while lo < hi:
sum = nums[lo] + nums[hi]
if sum < target:
while lo < hi and nums[lo] == left: lo += 1
elif sum > target:
while lo < hi and nums[hi] == right: hi -= 1
else:
res.append([left, right])
while lo < hi and nums[lo] == left: lo += 1
while lo < hi and nums[hi] == right: hi += 1
else:
# n > 2, recursive call
i = start
while i < sz:
sub = nSum(nums, n-1, i+1, target-nums[i])
for arr in sub:
res.append([nums[i]] + arr)
while i < sz - 1 and nums[i] == nums[i+1]:
i += 1
else:
i += 1
return res
There can be follow up: 100-sum.
