圖解「小於 K 的兩數之和 」
- 2019 年 10 月 4 日
- 筆記
者 | 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 < 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; }