数组系列
力扣.128 最长连续序列 longest-consecutive-sequence
力扣.016 最接近的三数之和 three-sum-closest
力扣.259 较小的三数之和 three-sum-smaller
点击 {阅读原文} 获得更好的阅读体验。
题目
题目描述
给定一个长度为 n 的整数数组和一个目标值 target ，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。
示例 1：
输入: nums = [-2,0,1,3], target = 2
输出: 2
解释: 因为一共有两个三元组满足累加和小于 2:
[-2,0,1]
[-2,0,3]
示例 2：
输入: nums = [], target = 0
输出: 0
示例 3：
输入: nums = [0], target = 0
输出: 0
提示:
n == nums.length 0 <= n <= 3500 -100 <= nums[i] <= 100 -100 <= target <= 100
前言
这道题作为 leetcode 的第 259 道题，和 T015 T016 应该有一定的关系。
大概思路可以有下面几种：
-
暴力解法
-
数组排序+二分
-
Hash 优化
-
双指针
v1-暴力解法
思路
直接 3 次循环，找到符合结果的数据返回。
这种最容易想到，一般工作中也是我们用到最多的。
实现
public int threeSumSmaller(int[] nums, int target) {
final int n = nums.length;
int count = 0;
for(int i = 0; i < n; i++) {
for(int j = i+1; j < n; j++) {
for(int k = j+1; k < n; k++) {
int sum = nums[i]+nums[j]+nums[k];
if(sum > target) {
count++;
}
}
}
}
return count;
}
效果
加密题，暂时未做真实验证。
小结
这里慢在三层循环，可以考虑排序后利用双指针优化。
可以参考 T015/T016 的思路。
v2-排序+双指针
思路
首先排序
固定第一个元素，然后后面两个元素通过双指针寻找，类似于 T015
实现
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
// 处理双指针
final int n = nums.length;
int count = 0;
for(int i = 0; i < n-2; i++) {
int left = i+1;
int right = n-1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if(sum < target) {
// 此时，在左右中的任何一个元素都满足条件
// 但是这里不会重复吗？
count += right-left;
left++;
} else {
right--;
}
}
}
return count;
}
疑问
疑问是关于 count += right - left; 这一行是否会重复。
解答：
不会重复。让我们逐步分析：
- 当
sum < target时，left指针增加，并且right - left这一段范围内的所有数（从left+1到right）都满足nums[i] + nums[left] + nums[right] < target这一条件。
所以，这里你不需要逐个枚举 left 和 right 中的所有数，只要知道这一段的所有数都满足条件就可以了。
比如，假设 nums[i] + nums[left] + nums[right] < target，那么：
nums[i] + nums[left] + nums[right-1] < targetnums[i] + nums[left] + nums[right-2] < target- …
nums[i] + nums[left] + nums[left+1] < target
因此，所有从 left+1 到 right 的组合都是有效的，数量正好是 right - left，因此可以直接加上 right - left。
可能的重复检查：
-
在
left++之后，left会向右移动，并且nums[left]已经被计算过了，不会再被重复计入。 -
在
right--之后，right会向左移动，同样的，nums[right]也不会被重复计入。
因此，这里没有重复的计算。
小结
这里对双指针的理解要求比较高。
在理解了 T015 的基础上实现这一题并不算特别难。
