アルゴリズムの問題:3の数の和は0です

タイトル
n個の整数を含む配列numsを与えて、numsの中に3つの要素a,b,cが存在するかどうかを判断して、a+b+c=0にしますか?条件を満たし、繰り返さないすべての三元グループを見つけてください.注意:答えに重複する三元グループは含まれてはいけません.例:所与の配列nums=[−1,0,1,2,−1,−4]であり、要求を満たす三元群の集合は[−1,0,1],[−1,−1,2]]である.
構想
この問題は典型的な二重ポインタの応用で、二重ポインタとこの問題の面接の出鏡率はすべてとても高くて、掌握することを提案します!この問題のアルゴリズムの構想は以下の通りである.

は、配列長nについて、配列がnullであるか、配列長が3未満である場合、直接[]を返すと特殊に判断する.

配列を並べ替える(並べ替えが必要で、そうでなければ判断やポインタ移動ができない).

ソート後の配列を巡回します.

nums[i]>0:並べ替えられているため、後に3つの数の加算が0に等しいことはありません.直接結果を返します.

繰り返し要素の場合:スキップし、繰り返し解

を回避

左ポインタL=i+1、右ポインタR=n-1、L

nums[i]+nums[L]+nums[R]=0の場合、要求を満たして要素を結果セットに追加し、ループを実行し、左境界と右境界が次の位置と重複しているかどうかを判断し、重複解を除去する.同時にL,Rを次の位置に移動し,新しい解

を探す.

和が0より大きいとnums[R]が大きすぎてRが

左にシフトすることを示す.

和が0未満であればnums[L]が小さすぎてLが

右にシフトすることを示す.

code

func getSum(nums []int) [][]int {
 var result [][]int //       
 length := len(nums) //       
 if nums == nil || length < 3 {
  return result
 }
 sort.Ints(nums) //   
 for i := 0; i < length; i++ {
  //         0，         0，      
  if nums[i] > 0 {
   break
  }
  //   ，   i   
  if i > 0 && nums[i] == nums[i-1] {
   continue
  }
  l := i + 1
  r := length - 1
  for {
   if l >= r {
    break
   }
   sum := nums[i] + nums[l] + nums[r]
   if sum > 0 {
    r --
    continue
   }
   if sum < 0 {
    l ++
    continue
   }
   if sum == 0 {
    result = append(result, []int{nums[i], nums[l], nums[r]})
    //   ，   l
    for l < r && nums[l] == nums[l+1] {
     l++
    }
    //   ，   r
    for l < r && nums[r] == nums[r-1] {
     r--
    }
    l++
    r--
   }
  }
 }
 return result
}