So lösen Sie das Problem der Summe dreier Zahlen in PHP

Bestimmen Sie bei einem gegebenen Array nums mit n ganzen Zahlen, ob es drei Elemente a, b, c in nums gibt, so dass a+b+c=0? Was sollen wir tun, wenn wir auf ein solches Problem stoßen? Heute werde ich Sie durch das Problem führen.

Angenommen, Sie haben ein Array nums mit n ganzen Zahlen. Bestimmen Sie, ob es drei Elemente a, b, c in nums gibt, sodass a + b + c = 0? Bitte finden Sie alle Tripel, die die Bedingungen erfüllen und sich nicht wiederholen.

Hinweis: Doppelte Tripel sind in der Antwort nicht zulässig.

Beispiel:

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

Ideen zur Problemlösung 1

Heftige Aufzählungsmethode, dreischichtig für +, wenn das Urteil ausreicht. Auf diese Weise wird das Angebot im Interview zu einem anderen. Wenn Sie keinen Code mehr schreiben, kommt es bei großen Datenmengen leicht zu einer Zeitüberschreitung.

Ideen zur Problemlösung 2

Sie können zuerst einen Wert festlegen und dann eine Doppelzeigermethode verwenden, um die letzten beiden Werte zu finden und so die Gesamtzeitkomplexität auf O(n^2) zu optimieren.

Während des Implementierungsprozesses sollte auf Optimierung und Deduplizierung geachtet werden.

Zuerst sortieren wir das ursprüngliche Array, sodass doppelte Werte gruppiert werden können, um die Deduplizierung zu erleichtern.

Wenn bei der Bestimmung des ersten Elements dieses bereits größer als 0 ist, kann man direkt aus der Schleife springen, da die nachfolgenden Zahlen alle größer als 0 sind. Zum Beispiel [1, 2, 3, 4], i = 0, nums[i] > es ist unmöglich, eine rechtliche Situation herzustellen, also brechen Sie einfach ab.

Wenn bei der Bestimmung des ersten Elements festgestellt wird, dass es mit dem Wert davor übereinstimmt, überspringen Sie diese Runde. Beispiel: [-1, -1, 0, 1], nach der ersten Runde wurde {-1, 0, 1} ausgewählt, jetzt ist i = 1, nums[i] == nums[i - 1], Um Doppelarbeit zu vermeiden, fahren Sie direkt fort.

Als nächstes verwenden Sie Doppelzeiger, linke Punkte auf i + 1 und rechte Punkte auf count($nums) - 1. Treffen Sie nacheinander Urteile und achten Sie darauf, Duplikate zu entfernen. Es ist ein bisschen so, als würde man einen Wert festlegen und dann zwei Zeiger verwenden, um die Summe der beiden Zahlen zu ermitteln.

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;
    }}

Empfohlenes Lernen: php-Video-Tutorial

Das obige ist der detaillierte Inhalt vonSo lösen Sie das Problem der Summe dreier Zahlen in PHP. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!