3 sum問題

配列を指定し、3つの数を0に加算したすべての組合せを見つけます.
例えば、0,1,−1,4,5,3,−7を与える
組み合わせは0,-1,1である.3, 4,-7
問題を解く構想:ここではa+b+c=0を要求し、a+b=-cを満たすだけでよい.まず配列をインクリメント順に並べ替え、ループすることで現在数が0より大きいとループから飛び出します.なお、現在数が前の数と等しく、現在数が0より大きい場合は、判断を続ける必要はなく、直接次の数にジャンプするだけでよい.

    vector> threeSum(vector& nums) {
        vector> res;
        sort(nums.begin(), nums.end());
        for (int k = 0; k < nums.size(); ++k) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue; //           ，          ，      
            int target = 0 - nums[k];
            int i = k + 1, j = nums.size() - 1;
            while (i < j) {
                if (nums[i] + nums[j] == target) {
                    res.push_back({nums[k], nums[i], nums[j]});
                    while (i < j && nums[i] == nums[i + 1]) ++i;
                    while (i < j && nums[j] == nums[j - 1]) --j;
                    ++i; --j;
                } else if (nums[i] + nums[j] < target) ++i;
                else --j;
            }
        }
        return res;
    }