无为清净楼资源网 Design By www.qnjia.com
三数之和
给你一个包含 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/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。逐个进行判断,并注意去重。有点类似于固定在一个值,然后剩下的用双指针求两数之和。
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; } }
参考链接:
- 三数之和的官方题解和高赞答案
- 极客时间 算法面试通关40讲
无为清净楼资源网 Design By www.qnjia.com
广告合作:本站广告合作请联系QQ:858582 申请时备注:广告合作(否则不回)
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
免责声明:本站文章均来自网站采集或用户投稿,网站不提供任何软件下载或自行开发的软件! 如有用户或公司发现本站内容信息存在侵权行为,请邮件告知! 858582#qq.com
无为清净楼资源网 Design By www.qnjia.com
暂无评论...
更新日志
2024年09月25日
2024年09月25日
- 黄心懋1991-轻忧郁【滚石】【WAV+CUE】
- 群星.2000-大地金曲世纪回顾2CD【大地】【WAV+CUE】
- 王菲.1996-浮躁(2024环球MQA-UHQCD限量版)【环球】【WAV+CUE】
- 群星.2022-传家电视剧原声带【东阳欢娱】【FLAC分轨】
- 《摇滚教父 伍佰黄金精选 2CD》 [WAV+CUE][1GB]
- 《凤凰传奇 我从草原来》[WAV/分轨][400MB]
- 《叶倩文 真心真意过一生》[WAV+CUE][400MB]
- 潘越云.1985-世间女子(滚石25周年经典复刻版)【滚石】【WAV+CUE】
- 陈柏宇.2009-CANT.BE.HALF【SONY】【WAV+CUE】
- 李明依.1989-小女生【滚石】【WAV+CUE】
- 《李荣浩 新时代创作新人王》[WAV分轨][310MB]
- 《黑鸭子与马头琴 史上最动听草原音乐》[WAV+CUE][320MB]
- 《汽车发烧音乐精选CD18》[FLAC+CUE][7.1G]
- 郑希怡.2004-Perfect.Date【英皇娱乐】【FLAC分轨】
- 群星.1994-宝丽金超级孖宝2CD【宝丽金】【WAV+CUE】