题目:15. 三数之和
如果您已经有思路了,或者是N刷了,可以先自己写一遍。
题目分析
题目说明:给定一个包含 n 个整数的数组 nums
,判断 nums
中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?找出所有满足条件且不重复的三元组。
注意,与两数之和不同,这里返回的是元素,不是下标。
解题思路
这个问题可以通过使用排序
和双指针
技术来解决。为了避免重复的三元组,首先应该对数组进行排序,然后通过两头夹逼法,找出所有可能的两个数和当前元素相加结果为0。
最重要的:题目中并没有规定不能有重复元素,为了避免添加重复的三元组,我们需要跳过数组中重复的元素。
具体步骤如下:
- 排序:首先,将数组排序。这是解决问题的前提,因为排序后可以使用双指针技术,并且更容易避免重复的三元组。
- 遍历:然后,遍历排序后的数组,对于每个元素,使用双指针找出所有可能的两个加数,使它们的和加上当前元素的值为0。
- 两头夹逼法:对于每个元素,我们在其之后的元素中设置左右指针,分别指向紧挨着这个元素的下一个元素和数组的最后一个元素。如果当前指针元素之和小于0,则移动左指针以增加总和;如果总和大于0,则移动右指针以减少总和。
- 避免重复:跳过重复的元素,以避免重复的三元组。
解题关键:排序 + 两头夹逼法 + 跳过重复元素
Java解法
下面是使用Java语言的解法:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| import java.util.ArrayList; import java.util.Arrays; import java.util.List;
public class Solution { public List<List<Integer>> threeSum(int[] nums) { Arrays.sort(nums); List<List<Integer>> result = new ArrayList<>(); for (int i = 0; i < nums.length && nums[i] <= 0; ++i) { if (i == 0 || nums[i - 1] != nums[i]) { resolve(nums, i, result); } } return result; } void resolve(int[] nums, int i, List<List<Integer>> result) { int lo = i + 1, hi = nums.length - 1; while (lo < hi) { int sum = nums[i] + nums[lo] + nums[hi]; if (sum < 0) { ++lo; } else if (sum > 0) { --hi; } else { result.add(Arrays.asList(nums[i], nums[lo++], nums[hi--])); while (lo < hi && nums[lo] == nums[lo - 1]) ++lo; } } } }
|
解法的时间复杂度主要由排序决定,排序的时间复杂度为 O(nlogn)
,遍历数组和双指针搜索的时间复杂度为 O(n^2)
。因此,总的时间复杂度为 O(n^2)
。
References