3Sum

ラベル(スペース区切り):C++アルゴリズムLetCode配列
毎日アルゴリズム-letcodeシリーズ
問題Longest Common Prefix
Difficulty: Medium
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)

The solution set must not contain duplicate triplets.

 For example, given array S = {-1 0 1 2 -1 -4}, 
 
A solution set is:
(-1, 0, 1)
(-1, -1, 2)
  
class Solution {
public:
    vector> threeSum(vector& nums) {
        
    }
};
  
  
   
   :  
n の  を つ  Sを え,a,b,cの3つの  がa+b+c=0を たすか かを  する.   のすべての たされた とゼロの3つの (  に  する3つの はありません).
  
$C_がランダムに つかった  n^3$のシナリオ.  を たす3つの をa,b,cと  し,この3つの インデックスはそれぞれi,j,kである. に べ えて、  の から1つの aを  して、bのインデックスはaより1 きくて、cは  の で、3  の  があります
 a+b+c=target i++k--この3つの を
に  する.
 a+b+c
 a+b+cを  するのが   よい.
コード#コード#

class Solution {
public:
    vector> threeSum(vector &nums) {
        vector > result;
        
        //   
        sort(nums.begin(), nums.end());
        int n = static_cast(nums.size());
        
        for (int i = 0; i < n - 2; ++i) {
            //    
            //                ，   0，0，0   
//            while (i < n -2 && nums[i] == nums[i+1]) {
//                i++;
//            }
             if (i>0 && nums[i-1] == nums[i]){
                 continue;
             }
            int j = i + 1;
            int k = n - 1;
            while (j < k) {
                if (nums[i] + nums[j] + nums[k] < 0){
                    //    
                    while (j < k && nums[j] == nums[j+1]) {
                        j++;
                    }
                    j++;
                }
                else if (nums[i] + nums[j] + nums[k] > 0){
                     //    
                    while (k > j && nums[k] == nums[k-1]) {
                        k--;
                    }
                    k--;
                }
                else{
                    result.push_back({nums[i], nums[j], nums[k]});
                    //    
                    while (j < k && nums[j] == nums[j+1]) {
                        j++;
                    }
                    while (k > j && nums[k] == nums[k-1]) {
                        k--;
                    }
                    j++;
                    k--;
                }
            }
        }
        return result;
    }
};