TwoSum 相關問題思路總結
- 2019 年 10 月 4 日
- 筆記
概述
TwoSum 作為 LeetCode 的第一題存在，想必大家應該對其並不陌生。如果僅僅是看這道題目本身，並不難，思想也特別的簡單。
但是關鍵問題在於，由這個問題演變出來的題目和思路比較多，而且存在著不少的細節問題，今天我們就借著具體的題目和思路來看看 TwoSum 還可以怎麼玩？
兩種思路
對於 TwoSum 類問題，總的來說有兩種大的方向，一種方向是藉助 Hash 表，另外一種是藉助排序，然後利用相向雙指針來解決問題，我們分別來看看：
1、Hash 表的做法
public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> remainValues = new HashMap<>(); for (int i = 0; i < nums.length; ++i) { if (remainValues.containsKey(target - nums[i])) { int anotherIndex = remainValues.get(target - nums[i]); return new int[] {i, anotherIndex}; } remainValues.put(nums[i], i); } return new int[] {-1, -1}; }
思路很簡單，遍曆數組，每訪問一個元素，先判斷其配對的元素是否在 Hash 表中，如果在的話就說明我們找到了答案，將其輸出即可，如果沒有找到，就將當前的元素放入 Hash 表中，以方便後面的元素來配對。
這裡因為題目要求輸出元素在數組中的位置，所以用 HashMap 來存儲訪問過的元素和其對應的 index。
我們再來分析一下其時空複雜度。
- 由於使用了 Hash 表，空間複雜度是 O(n) 的，另外就是最差的情況，數組中的每個元素都要遍歷到，因此時間複雜度也是 O(n)。
- 從時間上面來看，這個演算法肯定是最優的，這很好理解，你要在數組中尋找配對的答案，數組當中的數肯定都需要看一遍。
2、排序加雙指針的思路
public int[] twoSum(int[] n, int t) { if (n == null || n.length == 0) { return new int[0]; } Arrays.sort(n); int[] result = new int[2]; int l = 0, r = n.length - 1; while (l < r) { if (n[l] + n[r] == t) { result[0] = n[l]; result[1] = n[r]; return result; } else if (n[l] + n[r] < t) { l++; } else { r--; } } return new int[0]; }
這種思路的前提是題目沒有要求我們必須輸出元素在數組中的位置，因為排序會改變元素在數組中的位置，這裡，我們輸出元素本身即可。
這裡的思路就是一頭一尾兩個指針。
- 每次判斷的時候，我們將左右兩個指針指向的元素加起來的和與我們要找的 target 對比，如果比 target 小，也就是說明如果在左指針不變的情況下，左指針加上左右指針中間的任意一個元素都會比 target 小，這也說明左指針不可能是我們要找的答案，因此向右移動左指針。
- 如果是加起來和我們要找的 target 對比，比 target 大，分析類似，這時需要將右指針向左移動。
我們來看看這裡的時間複雜度，因為做了排序這麼一個操作，其時間複雜度就會是 O(nlgn) ，對於空間複雜度來說，這裡並沒有使用額外的空間，因此空間複雜度是常數級的 O(1)。
兩種方法都講完了，如果你有一些編程經驗的話，相信這些東西不難理解。
你有沒有想過這兩種方法分別比較適合什麼樣的情況呢，基於 TwoSum 問題，思考下面的變化：
- 如果題目要求輸出所有可能的答案，該怎麼處理？
- 如果題目要求輸出所有可能的答案，並且數組中有重複元素該怎麼處理？
- 如果題目要求找到比 target 小/大 的配對該怎麼處理？
- 如果要找出兩數之差等於 target 的配對，該如何進行？
- TwoSum 的解題思路是否可以拓展到 TreeSum 或者更多的配對？
上面的問題可能有些你曾想過，有些沒有，那麼就讓我們帶著上述的問題來看看具體的例題，熟練地將上述兩種方法應用到實際的題目中去。
變形題目分析
題目描述
題目還是 TwoSum，但是這時需要你返回所有可能的情況（不重複），並且數組中允許重複元素的出現。
題目解析
首先我們需要思考的是，使用之前提到的兩種方法中的哪一種會比較好。
是不是兩種方法都可以，你分析一下會發現其實兩種方法都是可行的，和之前的 TwoSum 不一樣的是，這時當找到答案後，需要繼續尋找，而不是直接返回。
但是由於數組中存在重複元素，因此兩種方法裡面都需要考慮去重的機制。
- 對於 Hash 表的方法來說，其實你並不清楚之前是否添加過相同的答案，因此我們考慮使用一個集合去存儲答案，保證答案的不重複性；
- 對於排序的方法來說，去重的方式有所不同，排完序後，相同的元素會挨在一起，對於之前考慮過的元素，我們只需要略過就行，指針的移動很好地保證了這一點。
這裡就展示排序實現的方法：
程式碼實現
public List<int[]> twoSum6(int[] nums, int target) { if (nums == null || nums.length < 2) return 0; Arrays.sort(nums); List<int[]> results = new ArrayList<>(); int left = 0, right = nums.length - 1; while (left < right) { int v = nums[left] + nums[right]; if (v == target) { int[] result = {nums[left], nums[right]}; results.add(result); left++; right--; while (left < right && nums[right] == nums[right + 1]) { right--; } while (left < right && nums[left] == nums[left - 1]){ left++; } } else if (v > target) { right--; } else { left++; } } return results; }
題目描述
題目來源於 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; }
題目描述
題目來源於 LeetCode 上第 170 號問題：兩數之和 III – 數據結構設計。
設計並實現一個 TwoSum 的類，使該類需要支援 add 和 find 的操作。
add 操作 – 對內部數據結構增加一個數。 find 操作 – 尋找內部數據結構中是否存在一對整數，使得兩數之和與給定的數相等。
示例 1:
add(1); add(3); add(5); find(4) -> true find(7) -> false
示例 2:
add(3); add(1); add(2); find(3) -> true find(6) -> false
題目解析
題目要求讓你實現一個數據結構，這個結構支援 「添加元素」 和 「TwoSum」 兩個功能。
這時你需要綜合兩種方法的優劣性來選擇。
首先是 Hash 表的方法，如果使用這個方法，我們不需要考慮太多的東西，元素來了直接扔進數組就行，也就是說 添加元素 操作只需要 O(1) 的時間複雜度就可以完成，但是 TwoSum 的完成需要額外 O(n) 的空間；
再來看看排序的方法，因為這裡插入元素我們需要保證元素有序，因此 添加元素 需要 O(n) 的時間，但是這裡 TwoSum 操作並不需要額外空間，綜合來考慮，因為 添加元素 和 TwoSum 操作都會比較頻繁，因此 Hash 表的方法在時間上面更優。
程式碼實現
private Map<Integer, Integer> elements; private int MAX_VALUE = Integer.MIN_VALUE; private int MIN_VALUE = Integer.MAX_VALUE; /** Initialize your data structure here. */ public TwoSum() { elements = new HashMap<>(); } /** Add the number to an internal data structure.. */ public void add(int number) { elements.put(number, elements.getOrDefault(number, 0) + 1); MAX_VALUE = Math.max(MAX_VALUE, number); MIN_VALUE = Math.min(MIN_VALUE, number); } /** Find if there exists any pair of numbers which sum is equal to the value. */ public boolean find(int value) { if (value < 2 * MIN_VALUE || value > 2 * MAX_VALUE) { return false; } for (int i : elements.keySet()) { if (i * 2 == value && elements.get(i) >= 2) { return true; } else if (i * 2 != value && elements.containsKey(value - i)) { return true; } } return false; }
題目描述
題目來源於 LeetCode 上第 15 號問題： 三數之和。
給定一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？找出所有滿足條件且不重複的三元組。
注意：答案中不可以包含重複的三元組。
例如, 給定數組 nums = [-1, 0, 1, 2, -1, -4]， 滿足要求的三元組集合為： [ [-1, 0, 1], [-1, -1, 2] ]
題目解析
三數之和，Hash 表以及排序的思路都是可行的。
但是這裡涉及到去重，這裡比較推薦的做法是排序加雙指針。
思路其實比較直觀，確定一個元素，然後去找另外兩個元素，這麼一來就把 3Sum 轉變成了 2Sum 的問題，這裡我兩個方法都實現了一下，你可以進行參考。
程式碼實現
排序加雙指針
// sort + two pointers public List<List<Integer>> threeSum(int[] nums) { if (nums == null || nums.length < 3) { return new ArrayList<>(); } Arrays.sort(nums); List<List<Integer>> results = new ArrayList<>(); for (int i = 0; i < nums.length - 2; ++i) { if ((i != 0) && (nums[i] == nums[i - 1])) { continue; } List<Integer> result = new ArrayList<>(); twoSum(results, nums, i + 1, -nums[i]); result = null; } return results; } private void twoSum(List<List<Integer>> results, int[] nums, int startIndex, int target) { int left = startIndex, right = nums.length - 1; while (left < right) { if (nums[left] + nums[right] > target) { right--; } else if (nums[left] + nums[right] < target) { left++; } else { List<Integer> result = new ArrayList<>(); result.add(-target); result.add(nums[left]); result.add(nums[right]); results.add(result); left++; right--; while ((left < right) && (nums[left - 1] == nums[left])) { left++; } while ((right > left) && (nums[right + 1] == nums[right])) { right--; } } } }
哈希表
// HashSet public List<List<Integer>> threeSum(int[] nums) { if (nums == null || nums.length < 3) { return new ArrayList<>(); } Arrays.sort(nums); Set<List<Integer>> resultsSet = new HashSet<>(); List<List<Integer>> results = new ArrayList<>(); for (int i = 0; i < nums.length - 2; ++i) { if ((i != 0) && (nums[i - 1] == nums[i])) { continue; } Set<Integer> existedValue = new HashSet<>(); for (int j = i + 1; j < nums.length; ++j) { if (!existedValue.contains(nums[j])) { existedValue.add(-nums[j] - nums[i]); } else { List<Integer> result = new ArrayList<>(); Collections.addAll(result, nums[i], -nums[j] - nums[i], nums[j]); resultsSet.add(result); } } existedValue = null; } results.addAll(resultsSet); return results; }
題目描述
題目來源於 LeetCode 上第 611 號問題：有效三角形的個數。
給定一個包含非負整數的數組，你的任務是統計其中可以組成三角形三條邊的三元組個數。
示例 1:
輸入: [2,2,3,4] 輸出: 3 解釋: 有效的組合是: 2,3,4 (使用第一個 2) 2,3,4 (使用第二個 2) 2,2,3
注意:
- 數組長度不超過1000。
- 數組裡整數的範圍為 [0, 1000]。
題目解析
題目要求選出三條邊，使得這三條邊能夠構成三角形，咋眼看上去這道題貌似和 TwoSum 沒啥關係。
但我們回顧一下中學時期學的東西，三邊構成三角形的條件是 任意兩邊之和大於第三邊，那是不是說我們需要把三條邊都組合配對考慮一下？其實不用，我們可以得出下面的結論
a < b < c && a + b > c => 三角形
如果已知三條邊的大小順序，那麼其實我們只需要比較一次即可。
你再看看這是不是我們熟悉的 TwoSum 變種問題 – 如果題目要求找到比 target 小/大 的配對該怎麼處理？
這個時候我們從右往左選定 c ，然後使用 TwoSum 來找出 a 、b 即可，由於題目只要求輸出個數，那麼就按照之前講的思路，直接相加即可。
程式碼實現
public int triangleCount(int[] S) { if (S == null || S.length == 0) { return 0; } Arrays.sort(S); int result = 0; for (int i = S.length - 1; i >= 2; --i) { int l = 0, r = i - 1; while (l < r) { if (S[i] < S[l] + S[r]) { // S[i] < S[l] + S[r] && S[i] > S[r] > S[l] result += r - l; // 直接加上可能的個數 r--; } else { l++; } } } return result; }
題目描述
題目來源於 LeetCode 上第 18 號問題： 四數之和。
給定一個包含 n 個整數的數組 nums 和一個目標值 target，判斷 nums 中是否存在四個元素 a，b，c 和 d ，使得 a + b + c + d 的值與 target 相等？找出所有滿足條件且不重複的四元組。
注意：
答案中不可以包含重複的四元組。
示例：
給定數組 nums = [1, 0, -1, 0, -2, 2]，和 target = 0。 滿足要求的四元組集合為： [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
題目分析
4Sum 的思路和 3Sum 的思路是一樣的，只不過這時我們需要先將其轉換成 3Sum 來處理，其實就是比 3Sum 多了一次選擇。
程式碼實現
public List<List<Integer>> fourSum(int[] nums, int target) { if (nums.length < 4) { return new ArrayList<>(); } Arrays.sort(nums); List<List<Integer>> results = new ArrayList<>(); for (int i = 0; i < nums.length - 3; ++i) { if (i != 0 && nums[i] == nums[i - 1]) { continue; } List<List<Integer>> subResults = threeSum(nums, i + 1, target - nums[i]); for (List<Integer> res : subResults) { res.add(nums[i]); results.add(res); } } return results; } private List<List<Integer>> threeSum(int[] nums, int start, int target) { List<List<Integer>> results = new ArrayList<>(); for (int i = start; i < nums.length - 2; ++i) { if (i != start && nums[i] == nums[i - 1]) { continue; } List<List<Integer>> res = twoSum(nums, i + 1, target - nums[i]); for (List<Integer> r : res) { r.add(nums[i]); results.add(r); } } return results; } private List<List<Integer>> twoSum(int[] nums, int start, int target) { List<List<Integer>> results = new ArrayList<>(); int l = start, r = nums.length - 1; while (l < r) { if (nums[l] + nums[r] < target) { l++; } else if (nums[l] + nums[r] > target) { r--; } else { List<Integer> result = new ArrayList<>(); result.add(nums[l]); result.add(nums[r]); results.add(result); r--; l++; while (l < r && nums[r] == nums[r - 1]) { r--; } while (l < r && nums[l] == nums[l + 1]) { l++; } } } return results; }
題目描述
給定一個 target，求出兩數之差等於 target 的情況。
題目解析
如果使用 Hash 表的做法，對於傳統的 TwoSum，我們找到的答案是滿足等式:
num1 + num2 = target
因此這個時候判斷的時候，我們只需要判斷 target - nums 在不在 Hash 表中即可，對於兩數之差的話，我們找到的答案是滿足等式：
num1 - num2 = target or num2 - num1 = target
在這種情況下，我們需要判斷 target + num 以及 num - target 即可，也就是相比之前，判斷條件不同且多了一個。
如果是使用排序加雙指針的方法呢？這其實是個打破思路局限的很好例子，這個時候我們需要用到同向雙指針了，兩個指針均從左向右移動，一前一後，用右邊的減去左邊的差值來和 target 做比較，如果小了，移動右指針，大了，移動左指針，等於，輸出答案。
程式碼實現
public int[] twoDiff(int[] n, int t) { if (n == null || n.length == 0) { return new int[0]; } Arrays.sort(n); int[] result = new int[2]; int l = 0, r = 1; while (r < n.length) { if (l == r) { r++; } if (n[r] - n[l] == t) { result[0] = n[l]; result[1] = n[r]; return result; } else if (n[r] - n[l] < t) { r++; } else { l++; } } return new int[0]; }
總結
TwoSum 相關的問題就分析到這裡，非常有趣的一點是，TwoSum 不僅可以擴展成 3Sum，4Sum，它也可以擴展為 KSum， 但是這裡就需要用到動態規劃的知識了，暫不在這裡討論。希望這次分享的內容對你有所幫助
