LeetCode 259. 较小的三数之和
目录
题目描述
题意分析
给一个整数数组和一个目标值
target，统计满足0 <= i < j < k < n且nums[i] + nums[j] + nums[k] < target的下标三元组的个数。要特别看清两点。第一，答案是个数，不是把三元组本身列出来，这意味着中间过程可以批量计数而不必逐个构造。第二，判定用的是下标互不相同并保序，不是值互不相同——即使数组里有重复值，只要下标不同就算作不同的三元组，所以绝对不能去重。这是本题与 15 题（三数之和）最本质的差别，也是最容易踩的坑。
条件是严格小于，不含等于。这决定了指针移动的判断必须写成
sum < target而不是<=。数组长度上限是 300，$O(n^2)$ 是 9 万次操作、$O(n^3)$ 是 2700 万次，理论上暴力都能过。但面试考的显然不是能不能过，而是能否给出 $O(n^2)$ 的标准解法，所以要按后者来写。
边界要想清楚：长度小于 3 时不存在任何三元组，答案是 0；
target可能非常小以至于没有任何组合满足，也可能非常大以至于所有 $\binom{n}{3}$ 个组合都满足。最后一个关键信号是：判定条件只关心三个数的和，与它们的原始下标顺序无关。既然如此，就可以自由地重排数组——排序不会改变答案。这条观察是所有 nSum 类题目的共同起点。
解法：排序 + 双指针
核心思路
暴力做法是三重循环枚举
i < j < k，逐个检查和是否小于target，复杂度 $O(n^3)$。瓶颈在于最内层那重循环：对每一对固定的(i, j)，它把所有k都试了一遍，但并没有利用任何结构信息。突破口是先排序。排序后数组单调不减，于是对固定的第一个数
nums[i]，剩下的问题变成「在有序子数组nums[i+1..n-1]中，有多少对(left, right)满足两数之和小于target - nums[i]」。有序性让我们可以用对撞双指针，把内层的 $O(n^2)$ 降到 $O(n)$。双指针的核心是一次判断能排除一整批候选，具体分两种情况。
若
nums[i] + nums[left] + nums[right] < target：因为数组有序，把右指针从right换成left+1到right之间的任何一个位置，第三个数只会更小或相等，和必然仍小于target。所以以当前left为第二个数的合法组合共有right - left个，可以一次性全部计入，然后left++去考察下一个第二个数。这个「批量计数」正是本题相对三数之和的独特之处，也是它必须问「为什么是right - left而不是right - left + 1」的地方——区间[left+1, right]的元素个数恰好是right - left。若和大于等于
target：当前这一对已经太大，而nums[right]是剩余候选里最大的，任何以它为第三个数、第二个数不小于nums[left]的组合都同样超标，所以right--排除它。维持的循环不变量是：所有第二个数下标在
[left, right]区间内、且尚未被计入的合法三元组，全部还在当前的搜索范围里。两个分支都只排除了确定不合法或已经计过数的组合，不变量得以维持；left == right时区间内不足两个数，搜索结束。外层枚举
i从 0 到n - 3，每个i独立跑一次双指针。因为答案按i分类互不重叠（每个三元组的最小下标唯一），直接累加即可，不会重复也不会遗漏。最后强调一次：本题不需要任何跳过重复元素的逻辑。三数之和要去重是因为它返回的是值三元组的集合，而本题统计的是下标三元组的数量，重复值对应的是不同的下标，必须全部计入。
解题步骤
- 先对数组排序：判定只依赖三数之和、与原始顺序无关，所以重排安全；排序换来的单调性是双指针能成立的唯一依据。
- 外层循环
i从 0 到n - 3：i是三元组里下标最小的那个，后面必须至少还留两个位置给left和right，所以上界是n - 3（写成i < n - 2）。这个上界同时让长度小于 3 的数组自然跳过整个循环——不过要注意n - 2在n为 0 或 1 时会是负数，Java 的int下没问题，循环条件直接不成立。- 每轮把
left置为i + 1、right置为n - 1：left从i的下一位开始保证了i < j，right从末尾开始保证了搜索范围最大。这两个初值必须在每轮外层循环里重置，共用会让后续的i搜不到任何东西。- 内层循环条件
left < right：需要两个不同的下标，相等时无法构成一对。写成<=会让同一个元素被用两次。- 计算
sum = nums[i] + nums[left] + nums[right]：三个数直接相加。数组元素范围较小时不必担心溢出，若面试官把值域放宽到 $2^{31}$ 附近，则需要用long或改成比较nums[left] + nums[right] < target - nums[i]。sum < target时执行count += right - left再left++：right - left是区间[left+1, right]的元素个数，也就是以当前left为第二个数的全部合法组合数。累加后当前left的所有情况都已穷尽，右移它换下一个第二个数。- 否则
right--：当前和太大，最大的那个第三个数必然无法与任何不小于nums[left]的第二个数配对成功，直接排除。- 返回
count：外层循环结束时所有以各个i打头的三元组都已统计完毕。以
nums = [-2, 0, 1, 3]、target = 2走一遍（题目样例，答案应为 2）。排序后数组不变，仍是
[-2, 0, 1, 3]，n = 4。
i = 0（nums[i] = -2）：left = 1、right = 3。第一轮sum = -2 + 0 + 3 = 1 < 2，说明left = 1配上[2, 3]区间里的任何一个都合法，count += 3 - 1 = 2（对应三元组(-2,0,1)和(-2,0,3)），left变成 2。第二轮sum = -2 + 1 + 3 = 2，不小于 2，right变成 2。此时left == right，内层结束。
i = 1（nums[i] = 0）：left = 2、right = 3。sum = 0 + 1 + 3 = 4 >= 2，right变成 2，内层结束，没有贡献。
i的上界是n - 2 = 2，i = 2时循环条件2 < 2不成立，外层结束。返回 2，与预期一致。
特别体会第一步的批量计数：如果那里只
count++而不是count += right - left，就会漏掉(-2, 0, 1)这一组，答案变成 1。再看重复值的用例nums = [0, 0, 0]、target = 1：排序后仍是[0,0,0]，i = 0时sum = 0 < 1，count += 2 - 1 = 1，left变成 2 与right相等结束，返回 1——三个 0 确实只能组成一个下标三元组(0,1,2)，如果加了「跳过相同值」的去重逻辑，这里会返回 0，直接错误。
代码实现
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;
}
}
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)$，其中 $n$ 是数组长度。排序是 $O(n \log n)$，被主体吞没；外层枚举 $n$ 个
i，每个i的双指针过程中left只增、right只减，两者合计移动不超过 $n$ 步，所以内层是 $O(n)$。- 空间复杂度：$O(1)$ 或 $O(\log n)$，取决于排序实现。算法本身只用了
i、left、right、sum、count几个标量；Java 的Arrays.sort对基本类型用双轴快排，递归栈是 $O(\log n)$，Go 的sort.Ints同理。
关键点总结
- 判定只依赖元素值的和时，排序是免费的——它不改变答案却带来单调性，是所有 nSum 类题目的第一步。能说清「为什么这里可以排序」比会写双指针更重要。
- 有序数组上的对撞双指针，价值在于一次判断排除一整批候选；本题更进一步，把「排除」升级成了「批量计数」，
count += right - left一行顶掉了整个内层循环。right - left而不是right - left + 1：计的是区间[left+1, right]的长度。凡是涉及区间计数的地方都要当场用一个小例子验一遍差一，这是最高频的错误来源。- 统计下标三元组个数时绝不能去重，而统计值三元组集合时必须去重。同一套双指针骨架在 15 题和本题上的分叉点就在这里，面试时被追问「为什么 15 要跳过重复而这里不用」，答「返回的是集合还是计数」即可。
- 求「小于某阈值的组合数」和求「等于某值的组合」在指针移动规则上不同：前者在和偏小时批量计数并右移左指针，后者在命中时才收集。写之前先明确条件是
<、<=还是==，可以避免整套逻辑写反。
易错点总结
sum < target时只写count++：[-2,0,1,3]、target = 2会返回 1 而不是 2，漏掉了同一个left配更小right的那些组合，这是本题第一大错误。- 写成
count += right - left + 1：多算了(left, left)这种自己配自己的非法组合，同一用例会返回 4；用[0,0,0]、target = 1验证时会返回 2 而正确答案是 1。- 照搬三数之和的去重逻辑：加上
while (left < right && nums[left] == nums[left+1]) left++之后，[0,0,0]、target = 1会返回 0，而正确答案是 1——本题统计下标三元组，重复值不能跳过。- 判断写成
sum <= target：题目要求严格小于，[0,0,0]、target = 0会返回 1 而正确答案是 0。- 忘记排序直接双指针：
[3,1,-2]、target = 2的对撞逻辑失去依据，sum与指针方向不再单调对应，结果随输入顺序变化。- 外层循环上界写成
i < n：i = n - 1时left = n、right = n - 1，内层条件不成立虽不会越界，但i = n - 2那轮同样凑不出三个数，白跑几轮；若把left初值误写成i则会直接把nums[i]用两次。left、right在外层循环之外初始化：第一轮结束后left已经逼近right，后续所有i的内层循环一次都不进，[-2,0,1,3]会返回 2 但[-2,0,1,3,4]这类需要多轮贡献的用例就会漏解。- 内层循环条件写成
left <= right：left == right时同一个元素被当作第二和第三个数，[1,1]配上任意i都会凭空多出组合。sum >= target时移动left而不是right：和只会变得更大或持平，right永远不动，循环退化成死循环或漏掉全部解。- 用三重循环暴力：$n = 300$ 时是 450 万次组合，能过判题但面试中会被要求优化；更糟的是很多人写暴力时把
j的起点写成 0 导致重复计数。count用int却担心溢出而加取模：$\binom{300}{3}$ 约 445 万，int完全装得下，取模反而会让答案错误。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 15. 三数之和 | 中等 | 返回值三元组集合，必须跳过重复元素去重，且条件是等于 0 而非小于 |
| LCR 007. 三数之和 | 中等 | 与 15 同题 |
| 16. 最接近的三数之和 | 中等 | 目标是最小化差值，每轮都要更新最优记录而不是计数 |
| 18. 四数之和 | 中等 | 多固定一层，需两重外层加双指针，且要注意四数求和的溢出 |
| 611. 有效三角形的个数 | 中等 | 同为批量计数，但固定最大边从后往前枚举，累加的是 right - left
|
| 1099. 小于 K 的两数之和 | 简单 | 本题去掉一层，求的是最大和而非组合数 |
| 167. 两数之和 II - 输入有序数组 | 中等 | 数组已有序无需排序，命中即返回下标，是对撞双指针的最简形态 |
| LCR 006. 两数之和 II - 输入有序数组 | 简单 | 与 167 同题 |
| 剑指 Offer 57. 和为s的两个数字 | 简单 | 与 167 同构，返回的是数值对而非下标 |
| 面试题 16.24. 数对和 | 中等 | 要求配对后移除，双指针命中时两侧同时收缩，也可用哈希计数做到 $O(n)$ |