文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

PHP怎么求解三数之和问题

2023-06-20 15:26

关注

本篇内容主要讲解“PHP怎么求解三数之和问题”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“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 {        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怎么求解三数之和问题”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯