PHP如何求解三數總和問題

給你一個包含n個整數的陣列nums，判斷nums中是否存在三個元素a，b，c ，使得a b c=0？當我們遇到這種問題的時候該怎麼辦，今天小編就帶大家來了解。

給你一個包含 n 個整數的陣列 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a b c = 0 ？請你找出所有符合條件且不重複的三元組。

注意：答案中不可以包含重複的三元組。

範例：

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

解題思路1

#暴力列舉法，三層 for if 判斷就可以了，這樣作面試中offer會成為別人的。不寫程式碼了，資料量大了也容易逾時。

解題思路2

可以先固定一個值，然後尋找後兩個值時可採取雙指標的方法，將總的時間複雜度最佳化到O(n^2)。

實現的過程中，要注意最佳化以及去重。

首先我們先對原數組進行排序，這樣可以把重複的值集中在一起，以便去重。

確定第一個元素時，如果它已經比 0 大了，那麼可以直接跳出循環，因為後面的數字都比它大。如 [1, 2, 3, 4], i = 0, nums[i] > 0, 這樣是不可能產生合法的情況的，直接 break。

確定第一個元素時，如果發現它與它前面的值一樣，那麼跳過本輪。如[-1, -1, 0, 1], 在第一輪後，已經選出了{-1, 0, 1}, 現在 i = 1，nums[i] == nums[i - 1],為了避免重複，直接 continue。

接下來利用雙指針，left 指向 i 1, right 指向 count($nums) - 1。逐一進行判斷，並注意去重。有點類似固定在一個值，然後剩下的用雙指標求兩數和。

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如何求解三數總和問題的詳細內容。更多資訊請關注PHP中文網其他相關文章！