18. 4Sum
Medium 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
How to solve the problem
- Hash Table Using Set Code
Python
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
n = len(nums)
res = set()
two_sum_map = defaultdict(list)
# Preprocess: store all pairs (i, j) whose sum is nums[i] + nums[j]
for i in range(n):
for j in range(i + 1, n):
two_sum = nums[i] + nums[j]
two_sum_map[two_sum].append((i, j))
# Search for two pairs whose sums add up to the target
for sum1 in two_sum_map:
sum2 = target - sum1
if sum2 not in two_sum_map:
continue
list1 = two_sum_map[sum1]
list2 = two_sum_map[sum2]
for (i, j) in list1:
for (k, l) in list2:
# Ensure all indices are distinct
if len(set([i, j, k, l])) == 4:
quad = sorted([nums[i], nums[j], nums[k], nums[l]])
res.add(tuple(quad)) # Use a set to avoid duplicates
# Convert the result back to list of lists
return [list(r) for r in res]
Complexity
- Time complexity: O(n^4)
- Space complexity: O(n)
Comments
No comments yet. Be the first to comment!