Python哈希表一招解決nSum問題

自古各門各家武學都存在套路，正所謂以不變應萬變，就在于臨戰之時，可以一招制敵，有的招數可能出奇制勝，但是最穩定的方式一定是多次訓練的套路，它不一定能讓你解決所有的問題，但是它足以讓你輕松應對一類問題，

nSum的問題，主要存在大量重復的數使得如果在陣列中遍歷每個數，再比較查詢結果，時間復雜度會超過題目的要求，我們可以采用哈希表的方式，加速查詢的程序，同時對遍歷的程序，對相同的數或者不滿足條件的數適當的跳過，可以有效的提升效率，通過測驗用例，

那么先從最簡單的兩數之和講起，

1、 Leetcode 1 兩數之和

最暴力的方式是從頭到尾列舉 nums 中的每一個數，然后再看是否在陣列中存在 j 使得 nums[j]  == target - nums[i] 且 j != i，這樣的方式，遍歷是 O(n) 復雜度，每次回圈在陣列中查詢也是 O(n) 復雜度，總的時間復雜度達到了 O(n^2)，代碼和運行時間如下：

 1 class Solution:
 2     def twoSum(self, nums: List[int], target: int) -> List[int]:
 3         result = []
 4         for i in range(len(nums)):
 5             if nums[i] in nums and target-nums[i] in nums:
 6                 j = nums.index(target-nums[i])
 7                 if i!=j:
 8                     result.append(i)
 9                     result.append(j)
10                     break
11         return result

這樣做顯然太過耗時，回圈如果不做改變的話（做改變的話可以用雙指標法，這里不做過多介紹），那么考慮在查找程序中進行加速，我們注意到哈希表中查找元素的時間是 O(1)，因此可以把在陣列中查找改為在哈希表中查找，對于這題而言，只要找到了答案就可以回傳，不需要找出所有的解，那么可以邊遍歷邊向哈希表中添加元素，添加前，查詢是否有滿足條件的解，如果滿足條件，return結果就可以，

1 class Solution:
2     def twoSum(self, nums: List[int], target: int) -> List[int]:
3         dic = {}
4         for i,num in enumerate(nums):
5             tmp = target - num # a + b = target, a = num, b = target - num
6             if tmp in dic:     # 哈希表中查詢是否有解
7                 return [i, dic[tmp]]
8             dic[num] = i       # 沒有解的話就存下當前的數和位置

運行結果如下：

最差的情況下，在線性時間內就可以解決問題

接下來考慮復雜一點的問題

2、 Leetcode 15 三數之和

首先題目要求解集里面不包含重復的元素，那么按照一定的規律找答案，就可以得到不重復的解，可以想到的方法是先進行排序，這樣就可以有規律的尋找了，排序以后，每個數也可能有多個重復的，假如每個解里不能包含相同的數字，那么簡單的在回圈里加上 

1 if i > index and nums[i] == nums[i-1]:
2     continue

其中 index 是回圈開始的值， 并且下一層回圈從 i + 1開始，就可以保證無重復了，這樣的去重方式可以參考我的另一篇文章講到的第三類問題， https://www.cnblogs.com/HMJIang/p/13575005.html 

然而這道題則是每個解里可以包含相同的數字，比如 [-1, -1, 2] 和 [0, 0, 0] 都可以得到和為0，這時候去重就可以用到Python中計數哈希表， Counter，先統計每個數字出現的次數，再對鍵值進行排序，每層回圈里判斷剩余的數字是否夠當前的變數選擇，

本題解法參考 https://leetcode-cn.com/problems/3sum/solution/ji-shu-zi-dian-jian-zhi-you-hua-fei-pai-xu-shuang-/

代碼如下：

 1 from collections import Counter
 2 class Solution:
 3     def threeSum(self, nums: List[int]) -> List[List[int]]:
 4         res = []
 5         dic = Counter(nums)  # Counter可以統計陣列每個元素的個數
 6         hash_nums = sorted(dic.keys()) #對鍵值進行排序
 7         for i, a in enumerate(hash_nums):
 8             dic[a] -= 1   # a已經取走了一個數字，字典里對應位置 -1
 9             for b in hash_nums[i:]:
10                 if dic[b] < 1: # b從i開始遍歷，i也是當前a的位置，如果減去1以后b不夠選了，跳過這一個位置
11                     continue
12                 c = -(a + b)
13                 if c < b:   #有序的查找，如果c都比b小，之后b再增大，肯定c更小，那么就跳出，防止重復
14                     break
15                 # 再判斷c和b的關系，如果相等，那就需要dic[c]至少為2，才夠選，如果不等，只要有，就夠選了
16                 if (c > b and dic[c] > 0) or (c == b and dic[c] > 1):
17                     res.append([a, b, c])
18         return res

時間復雜度 O(n^2)

空間復雜度 O(n)

提交結果：

有了這樣的經驗以后，我們可以用已有的套路看更復雜的四數之和

3、Leetcode 18  四數之和

最外層回圈遍歷到什么位置，就在對應位置上減1，接下來內層回圈里也把選擇的數減1，方便后面進行判斷，只要不夠選了，就continue跳過這一次回圈，如果最終的d比c還大，依舊break掉，和三數之和的差別在于，第二個數選擇的時候要減去1，最內層回圈結束以后還要加回1，因為之后最外層的a也會再遍歷到這個位置，

代碼如下：

 1 from collections import Counter
 2 class Solution:
 3     def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
 4         res = []
 5         dic = Counter(nums) #對每個數出現的次數進行統計
 6         arr = sorted(dic.keys())  #排序鍵值
 7         for i, a in enumerate(arr):
 8             dic[a] -= 1 #a用掉了一次，而且a的位置之后不會再遍歷到了，不需要加回
 9             for j, b in enumerate(arr[i:]):  #從arr[i]開始找b的值
10                 if dic[b] < 1: #b可能等于a，判斷一下，如果dic[b]不夠1個，跳過這次回圈
11                     continue
12                 dic[b] -= 1
13                 for c in arr[i+j:]:  #從arr[i+j]開始找c的值，注意上一層回圈列舉j以后，需要再加最外層的i
14                     if dic[c] < 1: #同上層回圈b的判斷
15                         continue
16                     d = target - (a + b + c)  
17                     if d < c:   #因為是非遞減順序，如果d小于c，就直接跳出，這樣就可以避免重復
18                         break
19                     if (d == c and dic[d] > 1) or (d > c and dic[d] > 0):
20                         res.append([a, b, c, d])
21                 dic[b] += 1 #b現在所處的位置，之后a還會遍歷到，因此需要加回1
22         return res

時間復雜度 O(n^3)

空間復雜度 O(n)

提交結果：

以此可以類推到更多數字的和，最外層回圈每選到一個位置以后，都減去1，內層的回圈也選到一個位置減去1，在更內層的回圈結束以后加回1就可以，最內層轉化為2數之間的大小關系的比較和查詢哈希表是否有滿足條件的值，

最后看一個變種問題

Leetcode 1577   數的平方等于兩數乘積的方法數

這一題如果暴力求解，必然超時，那么就需要一些優化策略，兩個陣列里可能會存在很多相同的數，它們僅僅是位置不同，找到的 j, k的結果卻一樣，比如 nums1 = [1,1,1,1]，nums2 = [1,1,1,1,1,1]，1中每個數的平方，都等于2中任意兩個不同位置的數的乘積，我們沒有必要對每個相同的 nums1 中的數都找一遍 nums2 中所有的數，這就又回到了 nSums 問題，可以想到的去重的方式是哈希表，

這里的技巧在于如果對于每個平方數去找是否存在兩個數和它相等，每個平方數遍歷的時間是 O(n)， 再找兩個數，如果要達到 O(m) 復雜度，就應該考慮雙指標的方式，然后需要各種比較，代碼相對復雜，容易出錯，如果換個思路，從右向左找，對于每個數字的乘積，都在哈希表里找是否存在相應的平方數，那么時間復雜度就是兩次遍歷陣列的時間復雜度 × 哈希表查找的時間復雜度，由于哈希表查找是 O(1)，最終等于兩次遍歷陣列的時間復雜度，

代碼如下：

 1 from collections import Counter
 2 class Solution:
 3     def numTriplets(self, nums1: List[int], nums2: List[int]) -> int:
 4         square1 = Counter([i*i for i in nums1])
 5         square2 = Counter([i*i for i in nums2])
 6         res = 0
 7         for i in range(len(nums2)):
 8             for j in range(i+1, len(nums2)):
 9                 tmp = nums2[i] * nums2[j] # 可以用tmp存一下兩數之積，避免后面字典查詢的時候再次重復計算鍵值
10                 if tmp in square1:
11                     res += square1[tmp]
12         for i in range(len(nums1)):
13             for j in range(i+1, len(nums1)):
14                 tmp = nums1[i] * nums1[j] # 同理
15                 if tmp in square2:
16                     res += square2[tmp]
17         return res

時間復雜度 O(n^2 + m^2)  其中 m，n 是 nums1 和 nums2 的陣列長度

空間復雜度 O(n+m)

代碼執行結果如下：

之所以說在每次回圈中要用 tmp 存一下兩數的乘積，因為隨著資料量的增加，重復計算兩數乘積的代價也是相當大的，如果兩次都直接用

1 if nums2[i] * nums2[j] in square1:
2     res += square1[nums2[i] * nums2[j]]

運行時間將會明顯提升，提交結果如下：

歡迎轉載，轉載請注明出處 ： https://www.cnblogs.com/HMJIang/

標籤：其他

上一篇：Gitlab 升級方案

下一篇：Github上傳專案步驟