怎样做投资网站,市场营销价格策略,注册域名后如何建立网站,如何开发软件程序点击蓝色“五分钟学算法”关注我哟加个“星标”#xff0c;天天中午 12:15#xff0c;一起学算法作者 | P.yh来源 | 五分钟学算法题目描述 题目来源于 LeetCode 上第 1099 号问题#xff1a;小于 K 的两数之和。给你一个整数数组 A 和一个整数 K#xff0c;请在该数组中找出… 点击蓝色“五分钟学算法”关注我哟加个“星标”天天中午 12:15一起学算法作者 | P.yh来源 | 五分钟学算法题目描述 题目来源于 LeetCode 上第 1099 号问题小于 K 的两数之和。给你一个整数数组 A 和一个整数 K请在该数组中找出两个元素使它们的和小于 K 但尽可能地接近 K返回这两个元素的和。如不存在这样的两个元素请返回 -1。示例 1输入A [34,23,1,24,75,33,54,8], K 60输出58解释34 和 24 相加得到 5858 小于 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 if (A[l] A[r] K) { r--; } else { result Math.max(result, A[l] A[r]); l; } } return result Integer.MIN_VALUE ? -1 : result;}有热门推荐?1.【程序员】全球最厉害的 14 位程序员2.【GitHub】我在 GitHub 上看到了一个丧心病狂的开源项目3.【算法】动画七分钟理解什么是KMP算法4.【数据结构】十大经典排序算法动画与解析看我就够了
