关于php:LeetCode-15PHP求解三数之和问题

41次阅读

共计 1565 个字符，预计需要花费 4 分钟才能阅读完成。

原文链接：何晓东博客

三数之和

给你一个蕴含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 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

暴力枚举法，三层 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;
    }
}

参考链接：