點擊藍色“五分鐘學算法”關注我喲
加個“星標”，天天中午 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 相加得到 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?????????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.【數據結構】十大經典排序算法動畫與解析，看我就夠了！
