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从前往后遍历，第二个数l从index+1开始，第三个数h从len-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;
    }
};