【LeetCode】三数之和双指针 Java 题解
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
复制代码
思路分析
今天的算法每日一题是三数之和题目,我们之前做过了两数之和题目,一般是采用 hashmap 来解决的。今天这个题目的解法,采用双指针的思想来解决。那什么是双指针呢?
双指针从广义上来说,是指用两个变量在线性结构上遍历而解决的问题。对于数组,指两个变量在数组上相向移动解决的问题;对于链表,指两个变量在链表上同向移动解决的问题,也称为「快慢指针」问题。
双指针算法通常不难,双指针算法是基于暴力解法的优化。
无论是对于两数之和,还是三数之和,我们需要首先保证数组有序,才能更好的使用这种结构。在无序的输入数组,需要首先排序。
对于三数之和排序去重,
复制代码
这个条件很常用,我们应该熟练掌握。
回到三数之和这个问题,我们把他拆解成两数之和问题。具体实现代码如下:
通过代码
复制代码
总结
上述代码的时间复杂度是 O(n * n), 空间复杂度是 O(n)
坚持算法每日一题,加油!
版权声明: 本文为 InfoQ 作者【HQ数字卡】的原创文章。
原文链接:【http://xie.infoq.cn/article/1c4b1592c50a62282688afe39】。文章转载请联系作者。
评论