15 三数之和
暴力解法(超时)
判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0
- 最简单的做法,三层循环就能找出三元组
[nums[i], nums[j], nums[k]]
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
for(int i = 0; i < n; i++){
for(int j = i + 1; j < n; j++){
for(int k = j + 1; k < n; k++){
if((nums[i] + nums[j] + nums[k]) == 0)
ans.push_back(vector<int> {nums[i],nums[j],nums[k]});
}
}
}
return ans;
}
};
但题目还要求:答案中不可以包含重复的三元组,因此我们需要去重
- 最直接的想法就是使用set/unordered_set,但是该类容器key值和value值相同,而key值通常不支持vector做元素
- 我们还可以从遍历上去重,可以想到,对数组进行排序,排序后,下一次遍历的元素与上一次相同时则跳过(因为上一个元素遍历过的元素,下一个元素还会重复一次)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < n; i++){
if(i > 0 && nums[i] == nums[i - 1])
continue;
for(int j = i + 1; j < n; j++){
if(j > i + 1 && nums[j] == nums[j - 1])
continue;
for(int k = j + 1; k < n; k++){
if(k > j + 1 && nums[k] == nums[k - 1])
continue;
if((nums[i] + nums[j] + nums[k]) == 0)
ans.push_back(vector<int> {nums[i],nums[j],nums[k]});
}
}
}
return ans;
}
};
时间复杂度:\(O(n^3)\)
空间复杂度:\(O(n^2)\)
通用框架
class Solution {
public:
vector<vector<int>> twoSumTarget(vector<int>& nums, int start, int target){
vector<vector<int>> res;
int left = start, right = nums.size() - 1;
while(left < right){
int sum = nums[left] + nums[right];
int left_val = nums[left], right_val = nums[right];
if(sum < target){
left++;
}else if(sum > target){
right--;
}else{
res.push_back({left_val, right_val});
while(left < right && nums[left] == left_val) left++;
while(left < right && nums[right] == right_val) right--;
}
}
return res;
}
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
// 这里for循环没有i++
for(int i = 0; i < nums.size(); ){
int val = nums[i];
vector<vector<int>> res = twoSumTarget(nums, i + 1, 0 - val);
for(vector<int>& tuple : res){
tuple.push_back(nums[i]);
ans.push_back(tuple);
}
while(i < nums.size() && nums[i] == val) i++;
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> twoSumTarget(vector<int>& nums, int start, int target){
vector<vector<int>> res;
int left = start, right = nums.size() - 1;
while(left < right){
int sum = nums[left] + nums[right];
if(sum < target){
left++;
}else if(sum > target){
right--;
}else{
res.push_back({nums[left], nums[right]});
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
left++;
right--;
}
}
return res;
}
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
// 这里for循环有i++
for(int i = 0; i < nums.size(); i++){
vector<vector<int>> res = twoSumTarget(nums, i + 1, 0 - nums[i]);
for(vector<int>& tuple : res){
tuple.push_back(nums[i]);
ans.push_back(tuple);
}
while(i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;
}
return ans;
}
};
容易忽略的细节
之所以给出两个写法的对比,是因为我在实现的时候发现,在跳过重复元素这部分我非常容易犯错。经过总结,我发现,这部分和删除重复元素思路完全一样,也是,跳过重复元素,不就是删除重复元素。
第一种:和未来比较。通过比较nums[i]和nums[i + 1]实现跳过重复元素
这种做法通过比较当前元素和下一个元素是否重复来跳过,那么什么时候结束:nums[i] != nums[i + 1]的时候,然而此时此刻的nums[i]仍然是最后一个重复元素
因此我们需要在末尾再添加一个i++
我们可以在写法二中的很多地方看到这种写法,这种比较方法是万能的,因为它能够指向最后一个重复元素,根据题意再判断是否需要保留最后一个重复元素,如果不需要,添加一行i++即可
方法二:和过去比较。记录第一个值nums[lo],通过比较nums[i]和nums[lo]`判断是否跳过后面元素
这种方法很关键的一点在于,它默认出现重复元素的时候保留第一个元素,因此和方法一相比具有局限性,但好处是不需要临界判断i + 1 < nums.size(),因为比较的是范围内的元素
写法一和写法二的区别用蓝色标注,twoSumTarget的两处地方容易发现,但是特别需要注意的是threeSum中的i的循环,for中的i++和跳过重复的while部分非常容易遗漏细节
代码还可以进一步优化,即使sum != target,遇到重复元素,也可以跳过,不过题意需要留下一个重复元素进行计算,有了前面的分析,这里你已经懂了。
class Solution {
public:
vector<vector<int>> twoSumTarget(vector<int>& nums, int start, int target){
vector<vector<int>> res;
int left = start, right = nums.size() - 1;
while(left < right){
int sum = nums[left] + nums[right];
if(sum < target){
while(left < right && nums[left] == nums[left + 1])
left++;
left++;
}else if(sum > target){
while(left < right && nums[right] == nums[right - 1])
right--;
right--;
}else{
res.push_back({nums[left], nums[right]});
while(left < right && nums[left] == nums[left + 1])
left++;
while(left < right && nums[right] == nums[right - 1])
right--;
left++;
right--;
}
}
return res;
}
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++){
vector<vector<int>> res = twoSumTarget(nums, i + 1, 0 - nums[i]);
for(vector<int>& tuple : res){
tuple.push_back(nums[i]);
ans.push_back(tuple);
}
while(i + 1 < nums.size() && nums[i] == nums[i + 1]) i++;
}
return ans;
}
};
优化版
三重循环还是时间花销太大了,我们想办法如何进一步优化
我们发现:假设nums[i] + nums[j] + nums[k] == 0 和nums[i] + nums[j] + nums[k + 1] == 0并且k > j + 1
那么第三层循环,k会重复遍历区间[j, k - 1]
为了避免这种情况,我们可以使用双指针
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> ans;
// 为什么要排序 -> 方便找出和为target的元素
sort(nums.begin(),nums.end());
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0)
return ans;
// 去重
if(i >= 1 && nums[i] == nums[i - 1])
continue;
int left = i + 1, right = nums.size() - 1;
// target为剩下两个数的和
int target = -nums[i];
// 为什么是< 因为求的是三元组
while(left < right){
if(nums[left] + nums[right] < target)
left++;
else if(nums[left] + nums[right] > target)
right--;
else{
ans.push_back({nums[i], nums[left],nums[right]});
// 去重
while(left < right && nums[left] == nums[left + 1]) left++;
while(left < right && nums[right] == nums[right - 1]) right--;
// 此时nums[left] != nums[left + 1] && nums[right] != nums[right - 1]
left++;
right--;
}
}
}
return ans;
}
};
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
for (int first = 0; first < n; first++) {
if (first > 0 && nums[first] == nums[first - 1])
continue;
int target = -nums[first];
int third = n - 1;
for (int second = first + 1; second < n; second++) {
if (second > first + 1 && nums[second] == nums[second - 1])
continue;
// 双指针需要保证左指针second < 右指针third
while (second < third && nums[second] + nums[third] > target){
third--;
}
// 如果两者相同,则说明不再存在b<c,与我们的前提假设b>c矛盾,因此结束
if(second == third)
break;
if(nums[second] + nums[third] == target)
ans.push_back({nums[first],nums[second],nums[third]});
}
}
return ans;
}
};