欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 15. 三数之和

程序员文章站 2022-07-15 11:18:45
...

LeetCode 15. 三数之和

方法一:暴力搜索

思路:三重循环遍历nums,每次选出的3个数先排序,再判重,最后压入ans数组

class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &numbers) {
        vector<vector<int>> ans;
        int len=numbers.size();
        for(int i=0;i<len;i++)
            for(int j=i+1;j<len;j++)
                for(int k=j+1;k<len;k++)
                    if(numbers[i]+numbers[j]+numbers[k]==0){
                        int nums[]={numbers[i],numbers[j],numbers[k]};
                    	sort(nums,nums+3);
                    	vector<int>tmp={nums[0],nums[1],nums[2]};                    
                        int is_repeat=0;
                        for (vector<vector<int>>::iterator it = ans.begin(); it != ans.end(); ++it)
                            if(*it==tmp) is_repeat=1; break;//有重复                   
                        if(is_repeat==0) ans.push_back(tmp);
                    }
        return ans;
    }
};

方法二:三指针法

思路:首先对nums进行升序排序。设3个指针,分别指向3个加数,第一个数index从前往后遍历,第二个数lindex+1开始,第三个数hlen-1开始,并且对数进行去重。若满足,则压入向量;若和太大则右指针左移;和太小则左指针右移。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> ans;
        int len = nums.size();
        if (len <= 2) return ans;
        int possible_len = len - 2;//一个数的可选长度
        sort(nums.begin(), nums.end());
        for (int index = 0; index < possible_len; index++) {//遍历第一个数
            int int_now = nums[index];//第一个数
            if (int_now > 0) break;//第一个数>0则直接退出循环
            int negative_now = 0 - int_now;//后面两个数的和
            int l = index + 1;//初始化左指针
            int h = len - 1;//初始化右指针
            while (l < h) {
                int int_l = nums[l], int_h = nums[h];//记录第二个和第三个数
                if (int_l + int_h == negative_now) {//若和满足,压入向量
                    vector<int> tmp{ int_now, int_l, int_h };
                    ans.push_back(tmp);
                    //左右指针去重
                    while (l < h && nums[l] == int_l) l++;//
                    while (l < h && nums[h] == int_h) h--;
                }
                else if (int_l + int_h < negative_now) l++;//和太小,左指针右移
                else if (int_h + int_h > negative_now) h--;//和太大,右指针左移
            }
            //去重
            while (index + 1 < possible_len && nums[index] == nums[index + 1]) index++;//第一个数去重
        }
        return ans;
    }
};
相关标签: LeetCode