LeetCode 259. 较小的三数之和
题目描述
给定一个整数数组 nums 和一个目标值 target，请统计满足以下条件的下标三元组 (i, j, k) 的个数：
0 <= i < j < k < nums.lengthnums[i] + nums[j] + nums[k] < target
示例 1：
输入：nums = [-2,0,1,3], target = 2
输出：2
解释：满足条件的三元组为 [-2,0,1] 和 [-2,0,3]。
示例 2：
输入：nums = [], target = 0
输出：0
示例 3：
输入：nums = [0], target = 0
输出：0
提示：
n == nums.length0 <= n <= 1000-100 <= nums[i] <= 100-100 <= target <= 100
题意分析
统计满足
i < j < k且三项和严格小于target的下标三元组数量。同一个值在不同位置出现时，这些位置分别参与组合，不能像“三数之和去重”那样跳过相同数值。只要求组合数量，不要求输出原下标，所以可以先排序。排序只是重新安排各次元素出现的位置，每组选中的三个位置仍对应同样的三个值，三项和不变，因而合法组合总数也不变。
解法：排序 + 双指针
核心思路
[!blue]
升序排序后，枚举第一项下标
i，剩余问题是在它右边选两个数，使两数和小于target-nums[i]。用left = i+1、right = n-1指向尚未处理范围的两端。若
nums[i]+nums[left]+nums[right] < target，在固定i和left后，第三项取[left+1,right]中任意位置都不会比当前right更大，因此全部合法，一次增加right-left。这些组合已全部计完，随后令left++，开始处理新的第二项。若当前和大于或等于目标，则固定
right后，任何位于[left,right)的第二项都不会比nums[left]更小，三项和也不可能合法。因此当前right不再有可计入的搭配，可以直接right--。每次移动都完整处理或排除了一个边界涉及的剩余组合，不会丢掉答案；同一个第二项只在左端前进时计数一次，不会重复。再让第一项依次取每个可能位置，每组三个排序后位置都按其最左位置归属到唯一一轮。
解题步骤
- 原地升序排序数组，令总数
count = 0。- 枚举
i = 0..n-3，每轮重新设置left = i+1、right = n-1。- 当
left < right时计算三项和：严格小于目标就累加right-left并移动左端，否则移动右端。- 指针相遇后，当前第一项下的组合已全部处理，继续下一轮，最后返回总数。
长度不足三时，外层循环自然不执行，答案为零。图中约束为
n <= 1000、元素在[-100,100]，三项和与最多 $\binom{1000}{3}=166167000$ 个组合都能由代码中的普通整数保存。
代码实现
class Solution {
// 使用左右指针统计满足 nums[i] + nums[l] + nums[r] < target 的数量。
public int threeSumSmaller(int[] nums, int target) {
Arrays.sort(nums);
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;
}
}
import "sort"
func threeSumSmaller(nums []int, target int) int {
// 使用左右指针统计满足 nums[i] + nums[l] + nums[r] < target 的数量。
sort.Ints(nums)
count := 0
for i := 0; i < len(nums)-2; i++ {
left, right := i+1, len(nums)-1
for left < right {
sum := nums[i] + nums[left] + nums[right]
if sum < target {
// 当前第二项配任意更小第三项都合法，一次计入整段数量
count += right - left
left++
} else {
right--
}
}
}
return count
}
复杂度分析
- 时间复杂度：$O(n^2)$，每个固定位置做线性扫描，排序不超过主体。
- 空间复杂度：扫描为 $O(1)$，总辅助空间由排序实现决定。
关键点总结
[!green]
- 排序提供单调性：第三项变小不会破坏“小于”，第二项变大也无法挽救“过大或相等”。
- 批量区间是
[left+1,right]，它不包含第二项自身，长度恰好为right-left。- 相同数值仍占据不同下标，每个位置组合都要计数，不做按值去重。
易错点总结
[!yellow]
- 不排序直接移动指针：无法保证移动后数值变大或变小，批量计数和排除边界都失去依据。
- 小于条件写成小于等于，会计入等于目标的组合。
- 只增加一，会漏掉同一左端对应的其他右项。
- 只因数值重复就跳过，会少计不同下标组合。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 15. 三数之和 | 中等 | 同样排序后固定一个值并对撞指针，本题发现和小于目标时可批量统计一整段右端选择。 |
| 16. 最接近的三数之和 | 中等 | 同样比较三数之和与目标，但原题只取最接近的一组，本题累计所有严格小于目标的下标组合。 |
| 18. 四数之和 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题满足阈值时批量累计指针对数，该题多固定一个数寻找四元组。 |
| 611. 有效三角形的个数 | 中等 | 排序后固定部分元素，再用左右指针收缩候选；本题满足阈值时批量累计指针对数，该题把三角不等式转为两数和比较。 |