首页 > 作文

关于PHP求解三数之和问题详析

更新时间:2023-04-08 23:54:27 阅读: 评论:0

三数之和

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。

注意:答案中不可以包含重复的三元组。

示例:

来源:力扣(leetcode) 链接:https://leetcode-cn.com/problems/3sum

解题思路 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。逐性格测试题个进行判断,并注意去重。有点类似于固定在一个值,然后剩下的用双指针求两数之和。

参考链接:

极客时间 算法面试通关40讲

到此这篇关于php求解三数之和问题的文章就介绍到这了,更多相关php求解三数之和内容请搜索www.887551.com以前的文章或继续浏览下面的相关文章希望大家以后多多支持www.887551.com!

本文发布于:2023-04-08 23:54:24,感谢您对本站的认可!

本文链接:https://www.wtabcd.cn/fanwen/zuowen/b776dd5dc953f6525d0ca45c354dc4f0.html

版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。

本文word下载地址:关于PHP求解三数之和问题详析.doc

本文 PDF 下载地址:关于PHP求解三数之和问题详析.pdf

标签:之和   指针   第一个   元素
相关文章
留言与评论(共有 0 条评论)
   
验证码:
Copyright ©2019-2022 Comsenz Inc.Powered by © 专利检索| 网站地图