跳转至

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]实现跳过重复元素

while(i + 1 < nums.size() && nums[i] == nums[i + 1]){
    i++;
}

这种做法通过比较当前元素和下一个元素是否重复来跳过,那么什么时候结束:nums[i] != nums[i + 1]的时候,然而此时此刻的nums[i]仍然是最后一个重复元素

因此我们需要在末尾再添加一个i++

while(i + 1 < nums.size() && nums[i] == nums[i + 1]){
    i++;
}
i++;

我们可以在写法二中的很多地方看到这种写法,这种比较方法是万能的,因为它能够指向最后一个重复元素,根据题意再判断是否需要保留最后一个重复元素,如果不需要,添加一行i++即可

方法二:和过去比较。记录第一个值nums[lo],通过比较nums[i]和nums[lo]`判断是否跳过后面元素

这种方法很关键的一点在于,它默认出现重复元素的时候保留第一个元素,因此和方法一相比具有局限性,但好处是不需要临界判断i + 1 < nums.size(),因为比较的是范围内的元素

int val = nums[i];
while(i < nums.size() && nums[i] == val){
    i++;
}

写法一和写法二的区别用蓝色标注,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;
    }
};