LeetCode 1099. 小于 K 的两数之和

2026-05-14 HGNULB 约 4 分钟

文章信息 8 个分类 · 4 个标签

分类

LeetCode CodeTop 简单 未解决 会员题 2-5 字节 阿里

标签

数组 排序 双指针 二分查找

题目描述

✅ 1099. 小于 K 的两数之和

给定一个整数数组 nums 和一个整数 k，请选择下标满足 i < j 的两个元素，返回小于 k 的两数和的最大可能值。如果不存在这样的两个元素，返回 -1。

示例 1：

输入：nums = [34,23,1,24,75,33,54,8], k = 60
输出：58
解释：可以选择 34 和 24，它们的和为 58，是小于 60 的最大可能值。

示例 2：

输入：nums = [10,20,30], k = 15
输出：-1
解释：不存在两数之和小于 15 的数对。

提示：

• 2 <= nums.length <= 100
• 1 <= nums[i] <= 1000
• 1 <= k <= 2000

题意分析

选择两个不同下标，使它们的和严格小于 k，并在所有合法和中取最大值。返回这个和，没有合法数对时返回 -1；两个数值可以相等，但不能重复使用同一个位置。

题面保证 1 <= nums[i] <= 1000，所以合法两数和一定为正，-1 可以同时作为未找到答案的标记和最大值初值。只要求返回和、不要求保留原下标，因此可以先排序，当前实现会重排输入数组。

解法：排序 + 双指针

核心思路

[!blue]

排序后，让 left、right 从两端向内移动。best 保存已经见过的最大合法和，每轮根据当前两数和能安全排除一个端点，避免枚举全部数对。

若 sum >= k，当前最小左值与 right 配对都不合法；在剩余区间内换成任何更大的左值，只会让和更大或不变。因此这个右端点不可能再产生合法数对，直接执行 right--。

若 sum < k，当前右端是剩余候选中的最大值，所以它已经给当前左端提供了最大的剩余合法配对和。先用它更新 best，再排除 left，尝试增大左值；与更小右端的配对不会改善刚记录的答案。

两种移动都只删除不可能带来更优答案的剩余数对，之前排除的数对也已被检查或证明无用，因此指针无需回退。相遇后不再有两个不同位置可选，返回历史最佳值；全程没有合法和时就保留负一。

解题步骤

1. 升序排序，初始化 left = 0、right = n - 1、best = -1。
2. 当 left < right 时计算当前和。
3. 和严格小于 k 时，用最大值比较更新 best，再右移左端点。
4. 和大于或等于 k 时，左移右端点；扫描结束返回 best。

代码实现

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;
    }
}

import "sort"

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+1))$。
• 空间复杂度：扫描 $O(1)$，另计标准库排序空间；会重排输入。

关键点总结

[!green]

• 不合法时排除最大右端，合法时先记录该左端的最佳剩余配对，再排除左端。
• 严格小于不包含等于，等于阈值时也要继续减小和。
• 正数值域保证合法结果大于 -1，初值不会压过真正的可行答案。
• 两个下标不同即可，数值相等仍可以配对。

易错点总结

[!yellow]

• 合法和不一定逐轮增大，不能直接覆盖历史答案，应取最大值。
• 和已经超界时增加左值，只会进一步增大和，不能修复当前右端。
• 条件写成 left <= right 会让同一下标被使用两次。
• 接受 sum == k 会违反严格小于要求。
• best = -1 依赖本题正数范围，不能不加说明地当作任意整数版本的最大值初始条件。

相似题目

题目	难度	关联与区别
167. 两数之和 II - 输入有序数组	中等	同样排序后双指针，本题在和小于k时更新最优并继续增大，而非找到精确和即结束。
259. 较小的三数之和	中等	把两数推广到三数，原题累计所有小于阈值的组合，本题只返回最大的合格和。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/34118172

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！