PHPで3つの数値の和の問題を解く方法

n 個の整数を含む配列 nums を与えて、nums に 3 つの要素 a、b、c (a b c=0) があるかどうかを調べます。このような問題に遭遇した場合はどうすればよいでしょうか?今日はそれについて説明します。

n 個の整数を含む配列 nums が与えられた場合、 a b c = 0 となる 3 つの要素 a、b、c が nums に存在するかどうかを判断します。条件を満たし、重複していないトリプルをすべて見つけてください。

注: 回答に重複したトリプルを含めることはできません。

例:

给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：[
 [-1, 0, 1],
 [-1, -1, 2]]

問題解決のアイデア 1

暴力的な列挙方法、判断が十分であれば、この方法で次のようなことができます。面接でのオファーは他の人のものになります。コードを書かなくなった場合、データ量が多いとタイムアウトになりやすくなります。

問題解決のアイデア 2

最初に値を固定し、次にダブル ポインター メソッドを使用して最後の 2 つの値を見つけ、合計時間を最適化できます。複雑さは O(n^2) になります。

実装プロセス中は、最適化と重複排除に注意を払う必要があります。

まず、元の配列を並べ替えて、重複した値を集めて重複排除を容易にします。

最初の要素を決定するときに、それがすでに 0 より大きい場合は、後続の数値がそれより大きいため、ループから直接抜け出すことができます。たとえば、[1, 2, 3, 4]、i = 0、nums[i] > 0 の場合、合法的な状況を作り出すことは不可能なので、単にブレークします。

最初の要素を決定するときに、その要素がその前の値と同じであることが判明した場合は、このラウンドをスキップします。たとえば、[-1, -1, 0, 1]、最初のラウンドの後、{-1, 0, 1} が選択され、i = 1、nums[i] == nums[i - 1]、重複を避けるため、直接続行してください。

次にダブル ポインターを使用します。左は i 1 を指し、右は count($nums) - 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;
    }}

推奨学習: php ビデオ チュートリアル

以上がPHPで3つの数値の和の問題を解く方法の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。