跳至主要內容

1099. 小于 K 的两数之和

ITCharge大约 1 分钟

1099. 小于 K 的两数之和open in new window

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

题目大意

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

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

解题思路

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

  • 先对数组进行排序(时间复杂度为 O(nlognO(n \log n),使用 res 记录答案,初始赋值为最小值 float('-inf')
  • 使用两个指针 leftrightleft 指向第 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