1099. 小于 K 的两数之和
大约 1 分钟
1099. 小于 K 的两数之和
- 标签:数组、双指针、二分查找、排序
- 难度:简单
题目大意
给你一个整数数组 nums
和整数 k
。
要求:返回最大和 sum
,满足存在 i < j
使得 nums[i] + nums[j] = sum
且 sum < k
。如果没有满足此等式的 i
, j
存在,则返回 -1
。
解题思路
常规暴力枚举时间复杂度为 。可以通过双指针降低时间复杂度。具体做法如下:
- 先对数组进行排序(时间复杂度为 ),使用
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