【LeetCode】三数之和 Java 题解
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
复制代码
思路分析
三数之和是数组类型题目,也是两数之和的进阶版。
对于数组类题目,对数组元素进行排序可以简化思路,提升算法效率。
这个题目还有一个难点是,不可以包含重复的三元组。具体对于每一层循环而言,相邻的元素不能相同。
三层循环的实现代码,在提交的时候显示超时,未通过。优化方向需要借鉴两数之和的思想,将 -nums[i] 设置为 target, 然后使用双指针,对排序数组从首尾进行遍历,得出答案。
通过代码
复制代码
总结
通过代码的时间复杂度是 O(n * n),快速排序使用了额外的空间,空间复杂度是 O(log n)
这是一个经典的题目,之前做过,但这次没有通过,要多总结,多反思,掌握好这个题目。
坚持每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/310065d0caf418ed9aec8480b】。文章转载请联系作者。
评论