leetcode15题解

2025-10-15

leetcode15题解

题目描述

给定一个整数数组 nums，返回所有满足以下条件的三元组 [nums[i], nums[j], nums[k]]：

  1. 索引 i、j、k 互不相等，即 i ≠ j、i ≠ k 且 j ≠ k；
  2. 三个元素的和为 0，即 nums[i] + nums[j] + nums[k] == 0。

注意，最终返回的解决方案集合中，不得包含重复的三元组。

解题思路

暴力

最朴素的想法一定是暴力解法，但是会超时。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int size=nums.size();
        int sum;
        vector<vector<int>> res;

        sort(nums.begin(),nums.end());
        int lasti=-99999;
        for(int i=0;i<size;i++){
            if(nums[i]>0) break;
            if(nums[i]==lasti) continue;
            lasti=nums[i];
            int lastj=-99999;
            
            for(int j=size-1;j>=i;j--){
                if(nums[j]<0) break;
                if (lastj==nums[j]) continue;
                lastj=nums[j];
                for(int k=i+1;k<j;k++){
                    if (nums[k]+nums[i]+nums[j]==0) 
                    {
                        res.push_back({nums[i],nums[k],nums[j]});
                        break;
                    }
                }
            }
        }
        return res;


    }
};

双指针

  • 在最开始考虑双指针的时候，我考虑的是先考虑左右两侧的限界，随后在中间找，三数之和大于零就让右指针向左移，否则左指针向右移，但是会发现这样会漏掉一部分结果，例如10=-5+-5，这样一高两低的办法导致了右指针更快地移走了，忽略掉了这个情况。
  • 于是先中间后两边。排序之后，先定义一个变量i，让i遍历所有可能的取值（注意并非所有值）。此时大于零右指针向左，小于零左指针向右即可找到所有解。吗？
    • 实际上并不是这样的，因为i在不同的位置，会有不同的左指针取值可能。i处于某一个同值簇的时候，左指针可以取到和i位置相同的值，带来差异，因此要在发现i与i-1相同时看看是否有这样的右指针找到一个正确的解。

结果如下：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int size=nums.size();
        int sum;
        vector<vector<int>> res;

        sort(nums.begin(),nums.end());
        //copy(nums.begin(),nums.end(),ostream_iterator<int>(cout," "));
        //cout<<endl;
        int lasti=INT_MIN;
        int i=0;
        while(i<size){
            if(i!=size-2&&nums[i]==nums[i+1]){
                for(int k=i+2;k<size;k++){
                    if(nums[i]+nums[i+1]+nums[k]==0){
                        res.push_back({nums[i],nums[i+1],nums[k]});
                        //cout<<"a"<<i<<" "<<i+1<<" "<<k<<endl;
                        break;
                    }
                }
            }
            do{
                ++i;
                if(i==size-1) break;
            }while(nums[i-1]==nums[i]);
            if(i==size-1) break;

            lasti=nums[i];
            int lp,rp;

            lp=0;
            rp=size-1;
            int lastlp=INT_MIN;
            int lastrp=INT_MAX;
            while(lp<i&&i<rp){
                if(nums[lp]+nums[i]+nums[rp]<0){
                    lastlp=nums[lp];
                    while(lastlp==nums[++lp]&&lp<i&&i<rp)
                        ;
                    
                }
                else if(nums[lp]+nums[i]+nums[rp]>0){
                    lastrp=nums[rp];
                    while(lastrp==nums[--rp]&&lp<i&&i<rp)
                        ;

                }
                else{
                    //copy(nums.begin(),nums.end(),ostream_iterator<int>(cout," "));
                    //cout<<endl;
                   
                    res.push_back({nums[lp],nums[i],nums[rp]});
                    //cout<<lp<<" "<<i<<" "<<rp<<" "<<endl;
                    
                    lastlp=nums[lp];
                    while(lastlp==nums[++lp]&&lp<i&&i<rp)
                        ;
                }

            }
        }
        return res;


    }
};