题目
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
1
2
3
4
5
6
7 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
[
[-1, 0, 1],
[-1, -1, 2]
]来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
题解
先考虑两数之和,找到所有可能的组合时间复杂度$O(N^2)$,可不可以用遍历一遍的时间解决?可以,从第一个数开始,对应的,我们都知道要找的是哪个数,这里就要空间换时间了,在一个暂存数组里存放无法配对的数字,每个新的数字都从里面找,这样只需遍历一次数组。
而三数之和的暴力法需要$O(N^3)$,用同样的思路空间换时间需要$O(N^2)$,难点在于怎么去重。
题解中先将数组排序,再用双指针加去重的方法就简单很多。
1 | class Solution { |