LeetCode 1099. 小于 K 的两数之和

2026-05-14 HGNULB 约 8 分钟

文章信息 7 个分类 5 个标签

分类

题目描述

✅ 1099. 小于 K 的两数之和

题意分析

输入一个整数数组和上界 k，要在所有「下标不同的两个元素」中，找出和严格小于 k 的最大和；一个合法数对都没有时返回 -1。

题目只关心和的数值，完全不要求返回下标，这说明元素的原始顺序是可以被破坏的，重排数组不会丢失任何信息，这是一条很强的信号：允许我们先把数据整理成有单调性的形态再处理。

数据量允许一次排序的开销，但不鼓励把所有数对都枚举一遍，所以目标是「排序 + 一次线性扫描」这一档的复杂度。

边界有三处：数组长度不足 2 时没有任何数对；所有数对的和都不小于 k 时必须返回 -1 而不是 0；判定条件是严格小于，和恰好等于 k 的数对不合法。

解法：排序 + 双指针

核心思路

最朴素的做法是二重循环枚举全部数对，对每个和小于 k 的组合取最大值。它一定正确，但要做约 $n^2/2$ 次加法，瓶颈在于左端点每换一次，右侧就要从头重新扫一遍，前一轮得到的信息全部被丢弃。

关键观察是：把数组升序排序后，固定左端点 left，和 nums[left] + nums[j] 关于 j 单调不减。于是「让和保持小于 k 的最大 j」这个位置，随着 left 右移只会往左走、不会往右回头——因为 left 变大后左边贡献更大，右端点只能更保守。既然右端点单调不回头，两个指针合起来只需要走 $O(n)$ 步。

由此可以显式写出扫描过程维护的不变量：在每一轮循环开始时，best 已经等于「至少有一端落在 [0, left) 或 (right, n-1] 的所有合法数对」中的最大和，因此仍可能超越 best 的数对必然两端都落在闭区间 [left, right] 内。

这个不变量之所以能一直成立，靠的是两条排除规则：若 nums[left] + nums[right] < k，那么对这个 left 来说 right 已是能取到的最大右端点，含 left 的最优数对就是当前这个，记录后 left 可以永久退出；若和不小于 k，那么 right 和任何 j >= left 配对都超界，right 可以永久退出。两种情况都只淘汰确定无用的元素，答案不会被误删。

解题步骤

先对 nums 升序排序。这一步是整个解法的前提：只有有序数组才具备「和随右端点单调」的性质，双指针的排除规则才成立。

初始化 left = 0、right = n - 1、best = -1。best 取 -1 而不是 0，是因为题目规定无解时返回 -1，把它当初值就不必在最后额外判断是否找到过答案。

循环条件写 left < right，保证两个指针指向不同下标。写成 left <= right 会让同一个元素和自己相加，构造出题目不允许的数对。

每轮计算 sum = nums[left] + nums[right]。若 sum < k，说明找到一个合法数对，用它更新 best；因为对当前 left 来说 right 已是最优右端点，继续留着 left 不会更好，所以 left 右移。

若 sum >= k，说明 right 太大，它与任何不小于 nums[left] 的元素相加都会越界，right 左移。注意此时不更新 best，因为这个和不合法。

循环结束返回 best：要么它保存着扫描过程中出现过的最大合法和，要么仍是初值 -1 表示无解。

以 nums = [34,23,1,24,75,33,54,8]、k = 60 走一遍：排序后数组为 [1,8,23,24,33,34,54,75]，下标 0 到 7，left = 0、right = 7、best = -1。

第一轮 1 + 75 = 76，不小于 60，right 降到 6。第二轮 1 + 54 = 55 < 60，best 更新为 55，left 升到 1。第三轮 8 + 54 = 62，不小于 60，right 降到 5。第四轮 8 + 34 = 42 < 60，比 55 小所以 best 保持 55，left 升到 2。第五轮 23 + 34 = 57 < 60，best 更新为 57，left 升到 3。第六轮 24 + 34 = 58 < 60，best 更新为 58，left 升到 4。第七轮 33 + 34 = 67，不小于 60，right 降到 4。此时 left 与 right 都等于 4，循环条件不成立，退出并返回 58。

注意第四轮那一步：和虽然合法却比已有答案小，说明「合法」和「更优」是两件事，更新 best 必须带上取最大值，直接赋值会把答案从 55 降到 42。

代码实现

class Solution {
    public int twoSumLessThanK(int[] nums, int k) {
        Arrays.sort(nums);

        int left = 0;
        int right = nums.length - 1;
        int best = -1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum < k) {
                best = Math.max(best, sum);
                left++;
            } else {
                right--;
            }
        }

        return best;
    }
}

func twoSumLessThanK(nums []int, k int) int {
    sort.Ints(nums)

    left, right := 0, len(nums)-1
    best := -1
    for left < right {
        sum := nums[left] + nums[right]
        if sum < k {
            if sum > best {
                best = sum
            }
            left++
        } else {
            right--
        }
    }

    return best
}

复杂度分析

时间复杂度：$O(n \log n)$，排序是主导项；排序之后 left 只增、right 只减，两者合计移动不超过 n 步，扫描部分只有 $O(n)$。

空间复杂度：$O(1)$，只用了三个整型变量；若把排序自身使用的栈空间计入，则为排序算法的 $O(\log n)$。

关键点总结

题目不要求返回下标时，排序几乎是免费的预处理，它能把「无结构的枚举」变成「有单调性的扫描」，这是 nSum 类问题的通用第一步。

双指针成立的前提永远是「某一侧指针的最优位置随另一侧单调移动」，写代码前先把这句单调性说清楚，才能保证移动指针不会漏解。

每次移动指针本质上是做一次批量排除，要能说出「被排除的那一批数对为什么都不可能更优」，这是面试官最想听到的论证。

无解时的返回值可以直接当作答案变量的初值，省掉一个「是否找到过」的布尔标记，代码更短也更不容易出错。

面试视角：说完双指针后主动补一句「也可以固定一端再二分找上界，$O(n \log n)$ 同阶但常数更大」，能体现你对解法空间的把握；如果面试官把 k 和值域限制在小范围，再顺势提一句可以用计数桶做到线性。

易错点总结

错误写法：把判定写成 sum <= k → 用例 nums = [1,2], k = 3，1 + 2 = 3 被当成合法解返回 3，正确答案是 -1。

错误写法：更新答案时直接 best = sum 而不取最大值 → 用例 nums = [1,8,23,24,33,34,54,75], k = 60，走到 8 + 34 = 42 那一步会把已经拿到的 55 覆盖成 42，最终返回 57 而不是 58。

错误写法：循环条件写成 left <= right → 用例 nums = [30], k = 61，left 和 right 都是 0，30 + 30 = 60 < 61 被当成合法数对，返回 60，但只有一个元素时根本组不成数对，正确答案是 -1。

错误写法：漏掉 Arrays.sort(nums) 直接跑双指针 → 用例 nums = [34,23,1,24,75,33,54,8], k = 60，未排序时和不再单调，指针移动的排除规则失效，返回 57 而不是 58。

错误写法：sum >= k 分支里也把 left 右移 → 用例 nums = [1,8,54,75], k = 60，第一轮 1 + 75 = 76 越界，left 被推到 1 后错过 1 + 54 = 55，最终返回 -1。

错误写法：best 初始化为 0 → 用例 nums = [10,20], k = 5，没有任何合法数对时返回 0，题目要求返回 -1。

错误写法：担心重复元素而在移动 left 时跳过所有相等值 → 用例 nums = [10,10], k = 25，去重逻辑把第二个 10 跳过，返回 -1，但 10 + 10 = 20 是合法答案 20；本题求的是和的最大值，不是去重的数对集合。

错误写法：在 sum < k 分支里同时移动 left 和 right → 用例 nums = [1,2,3,4], k = 100，第一轮 1 + 4 = 5 后两个指针一起动直接退出，返回 5，但最大合法和是 3 + 4 = 7。

错误写法：默认最优解一定包含数组最大值，把 right 固定在末尾只挪 left → 用例 nums = [1,2,3,100], k = 6，右端点被钉死在 100 上，任何组合都不合法，返回 -1，正确答案是 2 + 3 = 5。

相似题目

题目	难度	考察点
15. 三数之和	中等	外层固定一个数后套双指针，且必须跳过重复元素去重
16. 最接近的三数之和	中等	目标从「小于」变成「距离最近」，两侧都要更新候选答案
18. 四数之和	中等	两层固定加双指针，需要额外的溢出防护与剪枝
167. 两数之和 II - 输入有序数组	中等	数组已有序省掉排序，且要求返回下标而非和
259. 较小的三数之和	中等	同样是「小于」判定，但统计的是数对个数，一次加 right - left
611. 有效三角形的个数	中等	判定条件换成三角形不等式，需要固定最大边从右往左枚举
LCR 006. 两数之和 II - 输入有序数组	简单	精确命中目标值，和不合法时指针方向由大小关系唯一决定
LCR 007. 三数之和	中等	需要输出全部不重复三元组，考察结果集的去重实现
剑指 Offer 57. 和为s的两个数字	简单	只需返回任意一组解，找到即可提前退出
面试题 16.24. 数对和	中等	每个元素只能用一次，要在配对后同时收缩两个指针