LeetCode15-三数之和

LeetCode15-三数之和

双指针+排序

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
public List<List<Integer>> threeSum(int[] nums) {
//排序
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
//固定一个值target,范围从头到倒数第三位包含倒数第三位
for (int k = 0; k < nums.length - 2; k++) {
//如果固定值大于0,说明整体数组所有元素都大于0,就不可能存在相加等于0的情况
if (nums[k] > 0) break;
//如果固定值不是第一位,且当前固定值与前一个固定值相等,就跳过固定值
if (k > 0 && nums[k] == nums[k - 1]) continue;
//左指针为固定值的后一个,右指针为数组元素的最后一个
int l = k + 1, r = nums.length - 1;
while (l < r) {
//记录三数之和
int sum = nums[k] + nums[l] + nums[r];
//如果三个数小于0,说明左指针太小了,需要调大左指针,使整体的数之和更大一些
if (sum < 0) {
//跳过重复的左指针元素
while (l < r && nums[l] == nums[++l]) ;
//如果三个数大于0,说明右指针太大了,需要调小右指针,使整体的数之和更小一些
} else if (sum > 0) {
while (l < r && nums[r] == nums[--r]) ;
} else {
//反之就相等加到结果集合里去
res.add(new ArrayList<>(Arrays.asList(nums[k], nums[l], nums[r])));
//并且继续移动左右的指针并去重
while (l < r && nums[l] == nums[++l]) ;
while (l < r && nums[r] == nums[--r]) ;
}
}
}
return res;
}

本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!