题目描述:找出数组中任意4个数和为target的组合,不得重复。
题目链接:Leetcode 18. 4Sum
思路:基于3Sum做待定,相当又套了一层循环。
当然,也可以暴力列举 3 3 个的情况来达到目的。
代码如下
// Author: Huahua
class Solution {
public:
vector<vector<int>> fourSum(vector<int> &num, int target) {
set<vector<int>> h;
sort(num.begin(), num.end());
int n = num.size();
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for(int k = j + 1; k < n; k++) {
int t = target - num[i] - num[j] - num[k];
if (t < num[k]) break;
if (!std::binary_search(num.begin() + k + 1, num.end(), t)) continue;
h.insert({num[i], num[j], num[k], t});
}
}
}
return vector<vector<int>>(begin(h), end(h));
}
};
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort()
ans = []
if len(nums) < 4:
return []
for i in range(len(nums)-3):
fix = target - nums[i] #找到 此之后的数组 3个数相加和为target的数 当重复的时候就会跳过
if(i >= 1 and nums[i] == nums[i-1]):
continue
tmp = self.threeSum(nums[i+1:],fix) #接下来就是求3个和的问题
for sub in tmp:
sub.append(nums[i])
ans.extend(tmp) #添加结果
return ans
def threeSum(self, nums,k):
if len(nums) < 3:
return []
ans = []
for i in range(0,len(nums)-2): #到最后两个就停下
fix = k - nums[i] #需要fix的数 如果和前面一个数字相等 则continue k
if (i > 0 and nums[i] == nums[i-1]): #去重
continue
l = i + 1 #fix 数的下一个数 开始查询[l,r] 两个数相加和为 fix,注意去重。
r = len(nums) - 1 #需要fix的数的右边数组的右边界
while(l < r): #当左边界小于右边界时
curr_sum = nums[l] + nums[r]
if (curr_sum > fix): #太大了则右边往左
r -= 1
elif (curr_sum < fix): # 太小了往右
l += 1
else:
ans.append([nums[i],nums[l],nums[r]])
l += 1
r -= 1 # 此时继续寻找 因为仍然有可能
while(l < r and nums[l] == nums[l-1]):
l += 1 #跳过此l重复了
while(l < r and nums[r] == nums[r+1]): #更原来
r -= 1 #跳过这个r重复了
return ans