LeetCode 18. 四数之和
原题链接
中等
作者:
ShineShaye
,
2022-07-04 11:03:00
,
所有人可见
,
阅读 137
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
if(nums.size() < 4) return {};
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size() - 3; ++i)
{
if(i && nums[i] == nums[i - 1]) continue; // 判重*1
for(int j = i + 1; j < nums.size() - 2; ++j)
{
if(j > i + 1 && nums[j] == nums[j - 1]) continue; // 判重*2
for(int k = j + 1, u = nums.size() - 1; k < u; ++k)
{
if(k > j + 1 && nums[k] == nums[k - 1]) continue; // 判重*3,只有从后往前的指针不需要判重
// 题目中加和这一步数据会溢出,强制转换一下,数组中的值int是可以存的,不用都开long long
while(k < u - 1 && (long long)nums[i] + nums[j] + nums[k] + nums[u - 1] >= target) --u;
if((long long)nums[i] + nums[j] + nums[k] + nums[u] == target)
res.push_back({nums[i], nums[j], nums[k], nums[u]});
}
}
}
return res;
}
};