图解「小于 K 的两数之和 」
16lz
2021-01-22
题目描述
题目来源于 LeetCode 上第 1099 号问题：小于 K 的两数之和。
给你一个整数数组 A 和一个整数 K，请在该数组中找出两个元素，使它们的和小于 K 但尽可能地接近 K，返回这两个元素的和。
如不存在这样的两个元素，请返回 -1。
示例 1：
输入：A = [34,23,1,24,75,33,54,8], K = 60
输出：58
解释：
34 和 24 相加得到 58，58 小于 60，满足题意。
示例 2：
输入：A = [10,20,30], K = 15
输出：-1
解释：
我们无法找到和小于 15 的两个元素。
提示：
1 <= A.length <= 1001 <= A[i] <= 10001 <= K <= 2000
题目解析
传统的 TwoSum 都是要你找到等于 target 的配对，那么如果说要找到 大于/小于 target 的配对呢？
这个时候 Hash 表的方法就很难 work 了，因为 Hash 表比较适合处理 等于 的情况 ！
那么就需要考虑如何使用排序加双指针的方法来解决这个问题，这里，题目是要求小于 target 的数量，我们还是按照之前的分析思路来分析。
如果说当前左右指针指向的元素的和大于或者等于 target，那么势必我们需要向左移动右指针，让两个元素的和尽可能地小。
当前头尾指针指向的元素和小于 target 的时候，这时我们需要记录答案，虽然这道题目里面没提，如果说要记录配对数量的话，这时并不是记录一个答案，如果说当前左指针固定，除了当前的右指针指向的元素，在左指针和右指针之间的数都是满足要求的，我们只需要加上这个区间的数量即可。
当然如果数组中存在重复元素，那么我们就需要按照之前的套路遍历去重了，当然对于这道题来说，我们选择满足条件的最大值即可。
动画描述
代码实现
public int twoSumLessThanK(int[] A, int K) {
if (A == null || A.length == 0) {
return -1;
}
Arrays.sort(A);
int l = 0, r = A.length - 1;
int result = Integer.MIN_VALUE;
while (l < r) {
if (A[l] + A[r] >= K) {
r--;
} else {
result = Math.max(result, A[l] + A[r]);
l++;
}
}
return result == Integer.MIN_VALUE ? -1 : result;
}更多相关文章
- 动画：面试必刷之二维数组中查找一个元素
- 「复制带随机指针的链表」的一个很巧妙解法
- 前 K 个高频元素告诉你桶排序有啥用
- 使用快慢指针求解「环形链表」so easy！
- Python办公自动化｜光速对比并提取两份Word/Excel中的不同元素
- 动画: 快速排序 | 如何求第 K 大元素？
- php获取数组中最后一个元素的方法
- php实现获取数组中相同/不相同的元素
- 为什么推荐使用for-each而不是for循环遍历元素？