Leetcode之15-三数之和(3Sum)

算法题

题干

给定一个包含 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]
]

解法

  1. 暴力破解
  2. 单次循环之后转化为两数之和求解,两数之和采用HashSet求解
  3. 排序 + 单循环 + 双指针

复杂度

  1. 时间复杂度O(N^3)
  2. 时间复杂度O(N^2), 空间复杂度O(N)

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
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> data = new ArrayList<>(16);
final int LENGTH = nums.length;
final int LOOP_END_IDX = LENGTH - 2;
for (int i = 0; i < LOOP_END_IDX; i++) {
if (nums[i] > 0) {
break;
}
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int j = i + 1, k = LENGTH - 1;
while (j < k) {
int targetValue = -nums[j] - nums[k];
if (nums[i] == targetValue) {
data.add(Arrays.asList(nums[i], nums[j], nums[k]));
while (j < k && nums[j] == nums[j + 1]) {
j++;
}
while (j < k && nums[k] == nums[k - 1]) {
k--;
}
j++;
k--;
} else if (nums[i] > targetValue) {
k--;
} else {
j++;
}
}
}
return data;
}

代码解析

  1. 第7行代码表明如果当前元素大于零,没必要往后继续循环,后面不可能存在三数之后为零的情况
  2. 第10行代码,去重
  3. 第18-23行代码主要是找到与nums[j]、nums[k]值不同的索引位置,两个while循环最终得到的j和k都是与之前的nums[j]和nums[k]值相同的索引位置
  4. 第24-25行代码两指针j和k向中间靠拢,进入下一次循环。注意: 如果经过第18-23行两次while循环,同样需要j++,k- -操作

难点

  1. 对边界条件的精细处理
  2. 如何进行去重处理

思考题

  1. 解法三的时间复杂度是多少?
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%