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 < na,b,c, anddare distinct.nums[a] + nums[b] + nums[c] + nums[d] == target
Example:
Input: nums = [1, 0, -1, 0, -2, 2], target = 0
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]
Explanation: The unique quadruplets are:
[-2, -1, 1, 2]
[-2, 0, 0, 2]
[-1, 0, 0, 1]问题
给定一个包含 n 个整数的数组 nums，返回所有满足以下条件的唯一四元组 [nums[a], nums[b], nums[c], nums[d]]：
0 <= a, b, c, d < na、b、c和d是不同的。nums[a] + nums[b] + nums[c] + nums[d] == target
解决方案 1
排序 + 双指针方法
Approach 1 / 方法 1
This solution uses sorting and the two-pointer technique. The idea is to fix two elements and use two pointers to find the other two elements that sum up to the target.
该解决方案使用排序和双指针技术。其思想是固定两个元素，并使用两个指针找到其他两个元素，使它们的和等于目标值。
Implementation / 实现
python
# Solution 1 implementation in Python
def fourSum(nums, target):
nums.sort()
res = []
n = len(nums)
for i in range(n - 3):
if i > 0 and nums[i] == nums[i - 1]:
continue # Skip duplicate elements
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # Skip duplicate elements
left, right = j + 1, n - 1
while left < right:
s = nums[i] + nums[j] + nums[left] + nums[right]
if s < target:
left += 1
elif s > target:
right -= 1
else:
res.append([nums[i], nums[j], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1 # Skip duplicate elements
while left < right and nums[right] == nums[right - 1]:
right -= 1 # Skip duplicate elements
left += 1
right -= 1
return resExplanation / 解释
- Step 1 / 第一步:
- Sort the array
nums.
将数组nums排序。
- Step 2 / 第二步:
- Iterate through the array with two nested loops, fixing two elements at a time.
用两个嵌套循环遍历数组，每次固定两个元素。
- Step 3 / 第三步:
- Use two pointers (
leftandright) to find two other elements that sum up to the target with the fixed elements.
使用两个指针（left和right）找到另外两个元素，使它们与固定元素的和等于目标值。
- Step 4 / 第四步:
- If the sum is less than the target, move the
leftpointer to the right.
如果和小于目标值，将left指针右移。
- Step 5 / 第五步:
- If the sum is greater than the target, move the
rightpointer to the left.
如果和大于目标值，将right指针左移。
- Step 6 / 第六步:
- If the sum is equal to the target, add the quadruplet to the result and skip duplicate elements.
如果和等于目标值，将四元组添加到结果中，并跳过重复元素。
Complexity Analysis / 复杂度分析
-
Time Complexity: O(n^3), where n is the number of elements in the array.
时间复杂度: O(n^3)，其中n是数组中的元素数量。 -
Space Complexity: O(1), excluding the space required for the output.
空间复杂度: O(1)，不包括输出所需的空间。
Key Concept / 关键概念
- Sorting the array and using the two-pointer technique to find quadruplets efficiently.
排序数组并使用双指针技术高效地找到四元组。
解决方案 2
哈希表方法 (仅用于理解，复杂度较高)
Approach 2 / 方法 2
This solution uses a hash table to store the sums of pairs of numbers and then checks for the other two elements.
该解决方案使用哈希表存储成对数的和，然后检查另外两个元素。
Implementation / 实现
python
# Solution 2 implementation in Python
def fourSum(nums, target):
nums.sort()
res = set()
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
hashmap = {}
for k in range(j + 1, n):
complement = target - nums[i] - nums[j] - nums[k]
if complement in hashmap:
res.add(tuple(sorted([nums[i], nums[j], nums[k], complement])))
hashmap[nums[k]] = k
return list(res)Explanation / 解释
- Step 1 / 第一步:
- Initialize an empty set
resto store unique quadruplets.
初始化一个空集合res用于存储唯一的四元组。
- Step 2 / 第二步:
- Iterate through the array with two nested loops, fixing two elements at a time.
用两个嵌套循环遍历数组，每次固定两个元素。
- Step 3 / 第三步:
- Use a hash table to store complements of pairs of numbers and check for the other two elements.
使用哈希表存储成对数的补数，并检查另外两个元素。
- Step 4 / 第四步:
- If the complement is found in the hash table, add the sorted quadruplet to the result set.
如果在哈希表中找到补数，将排序后的四元组添加到结果集中。
Complexity Analysis / 复杂度分析
-
Time Complexity: O(n^3), where n is the number of elements in the array.
时间复杂度: O(n^3)，其中n是数组中的元素数量。 -
Space Complexity: O(n), due to the hash table.
空间复杂度: O(n)，由于哈希表。
Key Concept / 关键概念
- Using a hash table to find the other two elements for each pair of numbers.
使用哈希表为每对数找到另外两个元素。
Comparison / 比较
Comparison Between All Approaches
-
Algorithm:
-
Approach 1 (Sorting + Two-pointer Method):
- Sorts the array and uses two pointers to find quadruplets.
-
Approach 2 (Hash Table Method):
- Uses a hash table to store complements and find quadruplets.
-
-
Efficiency:
-
Time Complexity:
- Both approaches have a time complexity of O(n^3), where n is the number of elements in the array.
-
Space Complexity:
- The two-pointer method has a space complexity of O(1), excluding the output.
- The hash table method has a space complexity of O(n) due to the hash table.
-
-
Readability and Maintainability:
-
Approach 1 (Sorting + Two-pointer Method):
- Simple and efficient, making it easier to understand and maintain.
-
Approach 2 (Hash Table Method):
- Slightly more complex due to the use of a hash table.
-
-
Best Practice:
- Recommended Solution: Approach 1 (Sorting + Two-pointer Method):
- Reason: Approach 1 is preferred due to its simplicity, efficiency, and minimal space usage.
- Recommended Solution: Approach 1 (Sorting + Two-pointer Method):
Summary / 总结
- Use Approach 1 for a simple, efficient, and space-saving solution.
- Approach 1’s sorting and two-pointer method is straightforward and effective.
Tips / 提示
- Always sort the array first to simplify the two-pointer approach.
- Handle edge cases such as arrays with fewer than four elements or no valid quadruplets.
Solution Template for similar questions / 提示
- Use sorting and two-pointer methods to find quadruplets or pairs in array problems.
- Implement hash table methods for more complex scenarios if needed.
What does the main algorithm of this question aim to test? / 这个问题的主要算法旨在测试什么？
Understanding of sorting, two-pointer techniques, and hash table usage in array problems.
5 more
similar questions / 推荐5问题
- LeetCode 15. 3Sum
- LeetCode 1. Two Sum
- LeetCode 16. 3Sum Closest
- LeetCode 259. 3Sum Smaller
- LeetCode 167. Two Sum II – Input array is sorted
Recommended Resources:
4Sum – Leetcode 18 – Python by NeetCode
Leave a Reply