0%

刷算法(9)-较小的三数之和

259. 较小的三数之和(会员题)

给定一个长度为 n 的整数数组和一个目标值 target,寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数(0 <= i < j < k < n)。

1
2
3
4
5
输入: nums = [-2,0,1,3], target = 2
输出: 2
解释: 因为一共有两个三元组满足累加和小于 2:
  [-2,0,1]
[-2,0,3]

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int threeSumSmaller(int[] nums, int target) {
int result = 0;
Arrays.sort(nums);
for (int i = 0; i < nums.length; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.length - 1;

while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum < target) {
result += right - left;
left++;
} else {
right--;
}
}
}

return result;
}

心得

读题

注意题目要求是返回的满足要求的i、j、k三元组个数,这意味着如果有两个数字是重复的,虽然数值一样但是索引位置不同,也认为是不同的结果。所以进到for循环后,不能有nums[i] == nums[i-1]的剪枝操作,如果剪枝了直接答案会不对。

条件控制

这道题的关键在result += right - left;,即针对某个left,如果找到一个right满足要求小于了target,则right右边的数字一定是小于target的,因此直接得到个数right - left,然后让left移位。