4Sum
Given an array of integers `nums` and an integer `target`, return all unique quadruplets in `nums` that sum to `target`. The solution set must not contain duplicate quadruplets.
Constraints:
- 1 <= nums.length <= 200
- -109 <= nums[i] <= 109
- -109 <= target <= 109
Examples:
Input: [1, 0, -1, 0, -2, 2] and target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Explanation: The quadruplets in the input array that sum to the target are [-2, -1, 1, 2], [-2, 0, 0, 2], and [-1, 0, 0, 1].
Solutions
Two Pointers
The two pointers approach is used to solve this problem. First, we sort the input array. Then, we use two nested loops to fix the first two elements of the quadruplet. We then use two pointers, one starting from the next element of the second loop and one starting from the end of the array, to find the remaining two elements that sum to the target. If the sum of the four elements is equal to the target, we add the quadruplet to the result and move both pointers. If the sum is less than the target, we move the left pointer to the right. If the sum is greater than the target, we move the right pointer to the left.
def four_sum(nums, target):
nums.sort()
result = []
for i in range(len(nums) - 3):
for j in range(i + 1, len(nums) - 2):
left, right = j + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
result.append([nums[i], nums[j], nums[left], nums[right]])
left += 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
return resultFollow-up:
What if the input array is very large and we need to find all unique quadruplets that sum to the target in a more efficient way?
