【LeetCode(Java) - 1099】小于 K 的两数之和
【LeetCode(Java) - 1099】小于 K 的两数之和
文章目录
1、题目描述
2、解题思路
3、解题代码
1、题目描述
2、解题思路
??从一个无序数组找元素，第一个步骤就是先排序，否则只能暴力遍历。
??排序后，定义左右两个指针：left = 0; right = A.length - 1
??定义一个 res 变量保存小于 K 的最大值。
??1、如果 A[left] + A[right] < K ，说明还有往上加的空间，先把当前和跟 res 比较一下，保存最大值，left 往右移动一位；
??2、如果 A[left] + A[right] ≥ K ，说明超标了，得缩小一点，right 往左移动一位；
??3、当 left == right 时，说明已经没法移动了，res 保存的就是小于 K 的最大值。
3、解题代码
class Solution {
public int twoSumLessThanK(int[] A, int K) {
if (A == null || A.length == 0) return 0;
Arrays.sort(A);
int left = 0;
int right = A.length - 1;
int result = Integer.MIN_VALUE;
while (left < right) {
if (A[left] + A[right] < K) {
result = Math.max(result, A[left] + A[right]);
left++;
} else {
right--;
}
}
return result == Integer.MIN_VALUE ? -1 : result;
}
}
【LeetCode(Java) - 1099】小于 K 的两数之和相关教程
