1099. 小于 K 的两数之和

• 标签：数组、双指针、二分查找、排序
• 难度：简单

题目大意

给你一个整数数组 nums 和整数 k。

要求：返回最大和 sum，满足存在 i < j 使得 nums[i] + nums[j] = sum 且 sum < k。如果没有满足此等式的 i, j 存在，则返回 -1。

解题思路

常规暴力枚举时间复杂度为 $O(n^2)$。可以通过双指针降低时间复杂度。具体做法如下：

• 先对数组进行排序（时间复杂度为 $O(n \log n$），使用 res 记录答案，初始赋值为最小值 float('-inf')。
• 使用两个指针 left、right。left 指向第 0 个元素位置，right 指向数组的最后一个元素位置。
• 计算 nums[left] + nums[right]，与 k 进行比较。
  • 如果 nums[left] + nums[right] >= k，则将 right 左移，继续查找。
  • 如果 nums[left] + nums[rigth] < k，则将 left 右移，并更新答案值。
• 当 left == right 时，区间搜索完毕，判断 res 是否等于 fload('-inf')，如果等于，则返回 -1，否则返回 res。

代码

class Solution:
    def twoSumLessThanK(self, nums: List[int], k: int) -> int:

        nums.sort()
        res = float('-inf')
        left, right = 0, len(nums) - 1
        while left < right:
            total = nums[left] + nums[right]
            if total >= k:
                right -= 1
            else:
                res = max(res, total)
                left += 1

        return res if res != float('-inf') else -1