题解 | 三数之和

class Solution {
public:
    //求三数之和，从两数之和而来，一个循环固定一个数，循环内进行双指针：相当于求两数之和为第三数的相反值
    //考虑重复问题，同样，未使用或者正在使用是可以使用本数的，而相同的数使用过了，这个数就不能使用了，标记且跳过；
    vector<vector<int> > threeSum(vector<int>& num) {
        if(num.size() < 3)return {};  //不能成组时，直接返回，不然在指针赋值时，超出数组

        vector< vector<int> > ans = {};
        sort(num.begin(), num.end());

        vector<int> visit( num.size() , 0);  //其实可以不用标记，在重复时，直接跳过即可

        for(int i=0; i<num.size()-2; i++){
            if(i>0 && num[i] == num[i-1] && visit[i-1] == 2){
                visit[i] = 2;
                continue;
            }

            visit[i] = 1;
            int left = i+1;
            int right = num.size()-1;
            while(left < right){
                if( num[left]==num[left-1] && visit[left-1]==2 ){
                    visit[left] = 2;
                    left++;
                    continue;
                }

                if( right < num.size()-1 && num[right]==num[right+1] && visit[right+1] ==2 ){
                    visit[right] = 2;
                    right--;
                    continue;
                }

                if(num[left] + num[right] == -num[i]){
                    ans.push_back({num[i], num[left], num[right]});
                    visit[left] = 2;
                    visit[right] = 2;
                    left++;
                    right--;  //移动指针
                }else if( num[left] + num[right] < -num[i] ){
                    left++;
                }else if( num[left] + num[right] > -num[i] ){
                    right--;
                }
            }

            std::fill(visit.begin()+i+1, visit.end(), 0);  //清空记录
            visit[i] = 2;
        }

        return ans;
    }
};