Last Updated on 2022-07-20 by Clay
題目
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Notice that the solution set must not contain duplicate quadruplets.Example:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]這個題目是 2Sum、3Sum 的衍伸版，同樣給定一個整數陣列輸入，我們要找出由四個數加總為 0 的所有組合。
解題思路
這種題目的解題方法還挺固定的，在 4Sum 的題目中：
- 將輸入陣列從小排到大
- 使用兩層 for 迴圈，綁定陣列中固定的的起始兩值（不過會遍歷完整個陣列）
- 設定左端點和右端點，並將起始兩值、左右端點加總
- 加總值 > 0：將右端點往左走，試圖找更小總數的組合
- 加總值 < 0：將左端點往右走，試圖找更大總數的組合
- 加總值等於 0：此組為答案之一，若過去沒有找過這個組合的答案，即紀錄起來
C++ 程式碼
class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { // Init vector<vector<int>> results; sort(nums.begin(), nums.end()); // For-loop for (int i=0; i<nums.size(); i++) { for (int j=i+1; j<nums.size(); j++) { int left = j+1; int right = nums.size()-1; int temp_target = target - nums[i] - nums[j]; while (left < right) { int lr_sum = nums[left] + nums[right]; if (lr_sum == temp_target) { vector<int> result = {nums[i], nums[j], nums[left], nums[right]}; if (find(results.begin(), results.end(), result) == results.end()) { results.push_back(result); } left++; right--; } else if (lr_sum < temp_target) { left++; } else if (lr_sum > temp_target) { right--; } } } } return results; } };
(2022/07/20 更新)
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
// Init
vector<vector<int>> results;
sort(nums.begin(), nums.end());
long long_target = (long)target;
// For-loop
for (int i=0; i<nums.size(); i++) {
for (int j=i+1; j<nums.size(); j++) {
int left = j+1;
int right = nums.size()-1;
long temp_target = long_target - nums[i] - nums[j];
while (left < right) {
int lr_sum = nums[left] + nums[right];
if (lr_sum == temp_target) {
vector<int> result = {nums[i], nums[j], nums[left], nums[right]};
if (find(results.begin(), results.end(), result) == results.end()) {
results.push_back(result);
}
left++;
right--;
}
else if (lr_sum < temp_target) {
left++;
}
else if (lr_sum > temp_target) {
right--;
}
}
}
}
return results;
}
};Python 程式碼
class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: # Init results = [] nums = sorted(nums) # Find the result for i in range(len(nums)): for j in range(i+1, len(nums)): left = j + 1 right = len(nums) - 1 temp_target = target - nums[i] - nums[j] while left < right: lr_sum = nums[left] + nums[right] if lr_sum == temp_target: result = [nums[i], nums[j], nums[left], nums[right]] if result not in results: results.append(result) left += 1 right -= 1 elif lr_sum < temp_target: left += 1 elif lr_sum > temp_target: right -= 1 return results
C++ code gets Runtime Error..
Oops… It looks like be added some new test data, and the test data challenge the INT data type process limit.
A terrible solution is using “long” type to convert `target`. But as you can see that will be too slow.
I have no enough time to think a new way, sorry about that.
Maybe one day in future I’ll do that, but not right now.
Good Luck!
(I had updated my article, maybe you can refer it.)