题解 | #三数之和#

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param num int整型vector
     * @return int整型vector<vector<>>
     */
  //三数之和：转化成——有序中的两数和
  //a+b+c=0 (三数中一定要有负数，有正数)  看成a+b=-c 
  //去重：首先 排序 然后 按住一个数，后面结果 就是 a+ b = -c 在有序中找和为s的 所有两元组(要去重)遍历下一个按住的数,要看和上一个是否相等，如果相等就 跳过(continue ):
    void quicksort(vector<int>& num, int begin, int end) {
        if (num.size() == 0 || begin > end) return ;
        int left = begin, right = end;
        int tmp = num[left];
        while (left != right) {
            while (left < right && num[right] >= tmp) right--;
            num[left] = num[right];
            while (left < right && num[left] <= tmp) left++;
            num[right] = num[left];
            num[left] = tmp;
            if (left - 1 > begin) {
                quicksort(num, begin, left - 1);
            }
            if (left + 1 < end) {
                quicksort(num, left + 1, end);
            }
        }

    }
    void TwoSum(vector<int> array, int left, int right, int sum,
                vector<vector<int> >& res) {
                    cout<<sum<<" "<<left<<"  "<<right<<endl;
        while (left < right) {
            if ((array[left] + array[right]) > sum) right--;
            else if ((array[left] + array[right]) < sum) left++;
            else {
                res.push_back({-sum, array[left], array[right]});
                right--;
                left++;
                while (array[left] == array[left - 1]) left++;
                while (array[right] == array[right + 1]) right--;
            }
        }
    }
    vector<vector<int> > threeSum(vector<int>& num) {
        // write code here
        if (num.size() < 3) return{};
        quicksort(num, 0, num.size() - 1);
        for (int i = 0; i < num.size(); i++) {
            cout << num[i] << " " ;
        }
        cout<< endl;
        vector<vector<int> > res;
        for (int i = 0; i < num.size() - 2; i++) {
            while (i > 0 && num[i] == num[i - 1]) i++;
            if (i >= num.size() - 2) break;
            TwoSum(num, i + 1, num.size() - 1, -num[i], res);
        }
        return res;
    }
};