[LeetCode] 1099. Two Sum Less Than K

Given an array nums of integers and integer k, return the maximum sum such that there exists i < j with nums[i] + nums[j] = sum and sum < k. If no i, j exist satisfying this equation, return -1.

Example 1:

Input: nums = [34,23,1,24,75,33,54,8], k = 60
Output: 58
Explanation: We can use 34 and 24 to sum 58 which is less than 60.

Example 2:

Input: nums = [10,20,30], k = 15
Output: -1
Explanation: In this case it is not possible to get a pair sum less that 15.

Constraints:

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

小于 K 的两数之和。

给定一个数组 A，再给定一个数 k，要求找出 A 中的两个数，使得它们的和小于 k，返回这样的和里最大的那个和。
————————————————
版权声明：本文为CSDN博主「记录算法题解」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_46105170/article/details/105592564

题目不难，但是因为是带锁的题，所以记录一下。

时间O(nlogn)

空间O(1)

Java实现

 1 class Solution {
 2     public int twoSumLessThanK(int[] nums, int k) {
 3         Arrays.sort(nums);
 4         int left = 0;
 5         int right = nums.length - 1;
 6         int res = -1;
 7         while (left < right) {
 8             int sum = nums[left] + nums[right];
 9             if (sum < k) {
10                 res = Math.max(res, sum);
11                 left++;
12             } else {
13                 right--;
14             }
15         }
16         return res;
17     }
18 }

LeetCode 题目总结