LeetCode15.三数之和

更新: 1/31/2026 字数: 0 字时长: 0 分钟

题意大概就是找出三个数和为0(要求不能重复),与两数之和类似，我们很容易想到通过暴力枚举三次，时间复杂度 $O (N^{3})$ ,还需要通过加上hash表来，又需要开销大量的空间，使得时间复杂度和空间复杂度都不尽人意。

我们可以先对数组进行从小到大排序，从左到右进行枚举时可以判断当前这个是否与前一个相同，如果相同则跳过，这样就避免了重复的情况，因为我们将三个数的顺序固定成了从小到大依次排列并且不会重复。

对于后面两个数，我们当然可以暴力枚举，但是我们注意到如果第二个数发生了改变时，第三个数一定需要发生改变，那么我们可以用双指针进行优化，将两次遍历优化成数组每个数最多只需要枚举一次，总时间复杂度 $O (N^{2})$ 。

对于后面两个数，同样需要判断相同的情况。
case1: 如果和为0，则l++,r--;
case2: 如果和<0，则l++(因为需要更大的数);
case3: 如果和>0,则r--(因为需要更小的数);

Code:

c++

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> ans;
        sort(nums.begin(),nums.end());
        int a = 0,b = 0,c = 0;
        for(int i = 0;i < n - 2;i++) {
            a = nums[i];
            if(i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int l = i + 1,r = n - 1;
            while(l < r) {
                if(l > i + 1 && nums[l] == nums[l - 1]) {
                    l++;
                    continue;
                }
                if(r < n - 1 && nums[r] == nums[r + 1]) {
                    r--;
                    continue;
                }
                b = nums[l],c = nums[r];
                if(a + b + c == 0) {
                    ans.push_back({a,b,c});
                    l++,r--;
                }
                if(a + b + c < 0) {
                    l++;
                }
                if(a + b + c > 0) {
                    r--;
                }
            }
        }
        return ans;
    }
};

LeetCode15.三数之和 ​

LeetCode15.三数之和