【leetcode 15】三数の和Java題解

leetcode分類の下ですべての問題解は作者本人が比較した後に選んだ問題解であり、読みやすく、メンテナンス性に優れている.問題ごとに1つの答えしかなく、煩雑で実用的ではない案を避けたので、必ずしも最適解とは限らない.
n個の整数を含む配列numsを与え,numsにa,b,cの3つの要素が存在するか否かを判断し,a+b+c=0とする.条件を満たし、繰り返さないすべての三元グループを見つけます.
注意:答えに重複する三元グループは含まれてはいけません.
例えば、所与の配列nums=[−1,0,1,2,−1,−4],
要求を満たす三元群の集合は,[[−1,0,1],[−1,−1,2]]である.

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums.length < 3) return res;
        Arrays.sort(nums);
        int i = 0;                      //    1
        while(i < nums.length - 2){
            if(nums[i] > 0) break;      
            int j = i + 1;              //  2   1        
            int k = nums.length - 1;    //  3         
            while(j < k){
                int sum = nums[i] + nums[j] + nums[k];
                if(sum == 0) res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                if(sum <= 0) while(nums[j] == nums[++j] && j < k);
                if(sum >= 0) while(nums[k] == nums[--k] && j < k);  //nums[k--] == nums[k]  
            }
            while(nums[i] == nums[++i] && i < nums.length - 2);
        }
        return res;
    }
}

ソート

は3つのポインタを設定する:2つは前で、1つは後の

である.

while文によるポインタ

の再読み込みと移動