leetcode三数の和--二重ポインタ

タイトルリンク:三数の和タイトル説明:n個の整数を含む配列numsをあげて、numsの中に3つの要素a,b,cが存在するかどうかを判断して、a+b+c=0にしますか?条件を満たし、繰り返さないすべての三元グループを見つけてください.
注意:答えに重複する三元グループは含まれてはいけません.
例:
与えられた配列nums=[−1,0,1,2,−1,−4],
要求を満たす三元群の集合は,[[−1,0,1],[−1,−1,2]]である.
テーマ分析:肝心なのは繰り返さないことで、それでは繰り返さないために、まず配列を並べ替えることができて、同時に遍歴の過程の中で循環の下のスケールと隣接する要素が等しいかどうかの判断を制御して、重み付けの目的を達成します.続けて言えば、3つの数の和が固定されているため、私たちはその中の2つの数を知った後、3番目の数が確定しているので、1つの数を固定し、他の2つの数を列挙することができます.他の2つの数和は決定され、そのうちの1つが大きくなると、もう1つは必ず減少するので、2つのポインタを用いて双方向並列遍歴を行い、時間の複雑さを減少させることができる.本題の「二重ポインタ」では,配列中の2つの要素を列挙する必要がある場合,第1の要素が増加するにつれて第2の要素が減少することが分かった場合,二重ポインタ法を用いて,列挙の時間的複雑さをO(N 2)からO(N)に減少させることができる.なぜO(N)なのか.これは、列挙の過程の各ステップにおいて、「左ポインタ」が右に1つの位置(すなわち、タイトルのb)を移動し、「右ポインタ」が左にいくつかの位置を移動するため、配列の要素に関係するが、合計で移動する位置数はO(N)であり、均等に割り当てられ、毎回左に1つの位置を移動するため、時間の複雑さはO(N)であることが知られているからである.
コード:

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

似たような問題を補充します:最も近い3数の和はこの問題とほとんど同じ考えです

class Solution {
     
    public int threeSumClosest(int[] nums, int target) {
     
         Arrays.sort(nums);
         int ans = 1000000;
         for(int i = 0;i < nums.length;i++){
     
             if(i>0&&nums[i]==nums[i-1]) continue;
             int j = i + 1, k = nums.length-1;
             while(j<k){
     
                int sum = nums[i]+nums[j]+nums[k];
                if(sum==target) return target;
                if(Math.abs(sum-target)<Math.abs(ans-target))
                    ans = sum;
                if(sum>target){
     
                    k--;
                    while(j<k&&nums[k]==nums[k+1]) k--; //  ，                  
                }else{
     
                     j++;
                    while(j<k&&nums[j]==nums[j-1]) j++;//  
                }
             }
         }
         return ans;
    }
}