当前位置 博文首页 > 一条coding:【leetcode刷题】21.三数之和——Java版
?欢迎订阅《leetcode》专栏,每日一题,每天进步?
一题二写,三数之和,题解四瞅五瞄六瞧,水平还七上八下九流,十分辣鸡。
——leetcode此题热评
哈喽,大家好,我是一条。
糊涂算法,难得糊涂
现在遇题就想「动态规划」和「双指针」
难度:中等
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4] 输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = [] 输出:[]
示例 3:
输入:nums = [0] 输出:[]
提示:
0 <= nums.length <= 3000 -105 <= nums[i] <= 105
Solution
在这之前,我们做过两数之和。根据动态规划的思想,将问题拆解成一个数与另两个数的和互为相反数。
再利用双指针,计算另两数之和。
为了不得到重复解,先对数组进行排序。
首先对数组按升序进行排序,排序后固定一个数 ,再使用左右指针指向该数后面的两端,计算三个数的和是否为 0,满足则添加进结果集
考虑几种可能有重复解的情况
对于重复元素:跳过,避免出现重复解
等于0时,判断边界是否和下一个值重复,去除重复解
Code
所有
leetcode
代码已同步至github欢迎
star
/** * @author yitiaoIT */ class Solution { public static List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> 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<R && nums[L] == nums[L+1]) L++; // 去重 while (L<R && nums[R] == nums[R-1]) R--; // 去重 L++; R--; } else if (sum < 0) L++; else if (sum > 0) R--; } } return ans; } }
Result
复杂度分析
- 时间复杂度:O(N)
🌈寻宝
?今天是坚持刷题更文的第21/100天
?各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力
?更多算法题欢迎关注专栏《leetcode》
为了回馈各位粉丝,礼尚往来,给大家准备了一条多年积累下来的优质资源,包括 学习视频、面试资料、珍藏电子书等
怎么领取请大家自己找,寻宝游戏现在开始。
找不到可以评论留言,一条就会注意到你。
如果还不行,请私信我。
cs下一篇:没有了
最新 更多<<
一条coding:【leetcode刷题】21.三数之和——Java版 一条coding:【leetcode刷题】22.二叉树的中序遍历——Java版 一条coding:【leetcode刷题】23.对称二叉树——Java版 一条coding:【leetcode刷题】24.数组中重复的数字——Java版 一条coding:【一起去大厂】面试10多家中大厂后的万字总结——ja 一条coding:【leetcode刷题】25.二叉树的最大深度——Java版 一条coding:【leetcode刷题】26.翻转二叉树——Java版 一条coding:【leetcode刷题】27.二叉树的直径——Java版 一条coding:【leetcode刷题】28.替换空格——Java版 一条coding:CSDN热榜监控,一发布就被各路“大V”联合封杀 一条coding:【leetcode刷题】29.合并二叉树——Java版 一条coding:【leetcode刷题】30.青蛙跳台阶——Java版 一条coding:【leetcode刷题】31.旋转数组的最小数字——Java版 一条coding:【程序人生】从外包到大厂,你知道我这一个月是怎么 一条coding:【leetcode刷题】32.二进制中1的个数——Java版 一条coding:【leetcode刷题】33.最小的k个数——Java版 一条coding:【爆肝一周】面试10多家中大厂后的万字总结——??Ja 一条coding:【leetcode刷题】34.杨辉三角——Java版 大番薯:编程术语英汉对照 木木木 的博客:Linux下实现U盘自动挂载和卸载脚本 木木木 的博客:Qt开发之路1---Qt概述 木木木 的博客:Qt开发之路2---创建Qt项目 木木木 的博客:Qt开发之路3---main函数解读 木木木 的博客:Qt开发之路4---信号和槽机制 木木木 的博客:Qt开发之路5---Qt窗口系统 木木木 的博客:Qt开发之路6---QWidget 木木木 的博客:Qt开发之路7---QMainWindow 木木木 的博客:Qt开发之路8---对话框QDialog 木木木 的博客:Qt开发之路9---消息对话框QMessageBox 木木木 的博客:Qt开发之路10---文件对话框QFileDialog