[LeetCode 15]PHP三数の和を解く問題

原文リンク:のブログ
三数の和
n個の整数を含む配列numsを与えて、numsの中に3つの要素a,b,cが存在するかどうかを判断して、a+b+c=0にしますか?条件を満たし、繰り返さないすべての三元グループを見つけてください.
注意:答えに重複する三元グループは含まれてはいけません.
例:

     nums = [-1, 0, 1, 2, -1, -4]，

           ：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

ソース:LeetCodeリンク:https://leetcode-cn.com/probl...
問題を解く考え方1
暴力列挙法は、3階for + if で判断すればいいので、面接でofferが他人になることになります.コードを書かないと、データ量が多くなってもタイムアウトしやすい.
問題を解く考え方2
1つの値を固定してから、後の2つの値を探すときに、合計時間の複雑さをO(n^2)に最適化するために、2つのポインタの方法を採用することができる.
実装の過程では,最適化と重み付けに注意しなければならない.
まず、元の配列をソートします.これにより、重複した値を集中させ、重さを減らすことができます.
最初の要素を決定するときに、0より大きくなった場合は、後ろの数字が大きいため、ループから直接飛び出すことができます.[1, 2, 3, 4], i = 0, nums[i] > 0のように、これは合法的な状況を生み出すことは不可能であり、直接breakである.
最初の要素を決定するときに、前の値と同じ値が見つかった場合は、このホイールをスキップします.[−1,−1,0,1]のように、第1ラウンド後に{−1,0,1}が選出され、現在i = 1，nums[i] == nums[i - 1]であり、重複を避けるために直接continueである.
次に、leftはi + 1を指し、rightはcount($nums) - 1を指す.一つ一つ判断し、注意を払う.1つの値に固定され、残りは2つのポインタで2つの数の和を求めるのと似ています.

class Solution {

    /**
     * @param Integer[] $nums
     * @return Integer[][]
     */
    function threeSum($nums) {
        $result = [];
        $count = count($nums);
        if ($nums === null || count($nums) <= 2) return $result;

        sort($nums); // O(nlogn)

        for ($i = 0; $i < $count - 2; $i++) { // O(n^2)

            if ($nums[$i] > 0) break; //        0，        ，      

            if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue; //       

            $target = -$nums[$i];
            $left = $i + 1;
            $right = $count - 1;
            while ($left < $right) {
                if ($nums[$left] + $nums[$right] === $target) {
                    $result[] = [$nums[$i], $nums[$left], $nums[$right]];

                    //       left，   right，      ，  : [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3]       ，        -1   3

                    $left++;
                    $right--; //               

                    while ($left < $right && $nums[$left] === $nums[$left - 1]) $left++;
                    while ($left < $right && $nums[$right] === $nums[$right + 1]) $right--;
                } else if ($nums[$left] + $nums[$right] < $target) {
                    $left++;
                } else {  // $nums[$left] + $nums[$right] > $target

                    $right--;
                }
            }
        }

        return $result;
    }
}

参照リンク:

三数の和の公式問題解と高賛の答え

極客時間アルゴリズム面接通関40講

最後のチャペル阿里雲全シリーズ製品/メールパック特恵中小企業上雲ベスト選択阿里雲内部クーポン購入