Leetcode: 15. 3 Sum三数の和

Leetcode: 15. 3 Sum三数の和
問題の説明
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: The solution set must not contain duplicate triplets.
Example:
given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
与えられた配列Sにおいて、各群の3つの数の和が0になるように、すべての三元群が見出される.本題転送ゲート:https://leetcode.com/problems/3sum/
ソリューション
まずソートし、小さいから大きいまで最初の数を選択し、残りの区間で左右に挟みます.また、いくつかの不可能な状況を排除することで、スピードを上げることができます.{...,a,...,b→,,,←c,...}時間複雑度:O(n^2),空間複雑度:O(1),運転時間:39 ms,93.16%を超えるスキーム!

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> result;
        if(nums.size()<3) return result;//  3   ，   
        sort(nums.begin(),nums.end());//  
        const int target = 0;
        int a,b,c;//3      
        for(a=0;a2;a++){
            b=a+1;
            c=nums.size()-1;
            if(a>0 && nums[a]==nums[a-1])           continue;//    
            if(nums[a]+nums[a+1]+nums[a+2]>target)  break;//   
            if(nums[a]+nums[c]+nums[c-1]continue;//   
            while(bint sum=nums[a]+nums[b]+nums[c];
                if(sumwhile(b1])    b++;//    
                }else if(sum>target){
                    c--;
                    while(b1])    c--;//    
                }else{
                    result.push_back({nums[a],nums[b],nums[c]});//     
                    b++;c--;
                    while(b1])    c--;//    
                    while(b1])    b++;//    
                }
            }
        }
        return result;
    }
};