• 技术文章 >后端开发 >PHP问题

    PHP如何求解三数之和问题

    醉折花枝作酒筹醉折花枝作酒筹2021-07-13 15:16:45转载71
    给你一个包含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中文网其它相关文章!

    声明:本文转载于:何晓东的博客,如有侵犯,请联系admin@php.cn删除
    专题推荐:PHP
    上一篇:php怎么获取当前类的方法名 下一篇:php怎么设置文件大小限制
    第16期线上培训班

    相关文章推荐

    • php include出错怎么办• php 正则怎么去掉内容中的图片• php禁止输出错误的方法是什么• php怎么删除数组指定键的元素• php怎么获取当前类的方法名

    全部评论我要评论

  • 取消发布评论发送
  • 1/1

    PHP中文网