LeetCode题目:三数之和
发布日期:2021-11-18 19:17:45
浏览次数:14
分类:技术文章
本文共 1794 字,大约阅读时间需要 5 分钟。
题目描述:
给你一个包含 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 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。解答:
思路:
标签:数组遍历 首先对数组进行排序,排序后固定一个数 nums[i],再使用左右指针指向 nums[i]后面的两端,数字分别为 nums[L] 和 nums[R],计算三个数的和 sum 判断是否满足为 00,满足则添加进结果集 如果 nums[i]大于 0,则三数之和必然无法等于 0,结束循环 如果 nums[i] == nums[i−1],则说明该数字重复,会导致结果重复,所以应该跳过 当 sum == 0 时,nums[L] == nums[L+1] 则会导致结果重复,应该跳 过,L++ 当 sum == 0 时,nums[R] == nums[R−1] 则会导致结果重复,应该跳过,R– 时间复杂度:O(n^2)O(n2),nn 为数组长度代码(Java):
class Solution { public static List
> threeSum(int[] nums) { List
> ans = new ArrayList(); int len = nums.length; if(nums == null || len < 3) return ans; Arrays.sort(nums); // 排序 for (int i = 0; i < len ; i++) { if(nums[i] > 0) break;// 如果当前数字大于0,则三数之和一定 //大于0,所以结束循环 if(i > 0 && nums[i] == nums[i-1]) continue; // 去重 int L = i+1; int R = len-1; while(L < R){ int sum = nums[i] + nums[L] + nums[R]; if(sum == 0){ ans.add(Arrays.asList(nums[i],nums[L],nums[R])); while (L 0) R--; } } return ans; }}
作者:guanpengchn
链接:https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。作者:guanpengchn
链接:https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。转载地址:https://blog.csdn.net/weixin_39224015/article/details/105630197 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
第一次来,支持一个
[***.219.124.196]2024年03月30日 13时25分49秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
系统架构设计笔记(41)—— 系统过渡计划
2019-04-26
系统架构设计笔记(42)—— 软件架构概述
2019-04-26
系统架构设计笔记(57)—— 测试自动化与面向对象的测试
2019-04-26
系统架构设计笔记(58)—— 嵌入式系统概论
2019-04-26
说说 Python 的生成器表达式
2019-04-26
说说 Activiti 中的用户与组的概念
2019-04-26
系统架构设计笔记(62)—— 嵌入式数据库管理系统
2019-04-26
系统架构设计笔记(63)—— 实时嵌入式操作系统
2019-04-26
说说如何使用 Canvas 绘制弧线与曲线
2019-04-26
系统架构设计笔记(64)—— 嵌入式系统设计
2019-04-26
系统架构设计笔记(65)—— 项目的范围、时间与成本
2019-04-26
系统架构设计笔记(66)—— 配置管理与文档管理
2019-04-26
说说 Python 元组的高级用法
2019-04-26
系统架构设计笔记(66)—— 配置管理与文档管理
2019-04-26
系统架构设计笔记(67)—— 软件需求管理
2019-04-26
系统架构设计笔记(68)—— 软件开发的质量与风险
2019-04-26
系统架构设计笔记(69)—— 人力资源管理
2019-04-26
系统架构设计笔记(70)—— 软件运行评价与过程改进
2019-04-26
系统架构设计笔记(71)—— 信息系统概述
2019-04-26
说说 Canvas 的旋转功能
2019-04-26