1. 算法訓(xùn)練營(yíng)第七天哈希與雙指針實(shí)戰(zhàn)今天繼續(xù)代碼隨想錄算法訓(xùn)練營(yíng)的第七天內(nèi)容主要解決四個(gè)經(jīng)典問題454.四數(shù)相加II、383.贖金信、15.三數(shù)之和和18.四數(shù)之和。這幾個(gè)問題涵蓋了哈希表和雙指針兩大核心算法技巧是面試中的高頻考點(diǎn)。我會(huì)結(jié)合自己的刷題經(jīng)驗(yàn)詳細(xì)解析每個(gè)問題的解題思路和實(shí)現(xiàn)細(xì)節(jié)。2. 454.四數(shù)相加II哈希表的巧妙應(yīng)用2.1 問題重述與初步分析給定四個(gè)整數(shù)數(shù)組nums1、nums2、nums3和nums4數(shù)組長(zhǎng)度都是n。我們需要計(jì)算有多少個(gè)元組(i,j,k,l)滿足 nums1[i] nums2[j] nums3[k] nums4[l] 0最直觀的暴力解法是四重循環(huán)時(shí)間復(fù)雜度O(n^4)這在n200時(shí)顯然不可行200^41,600,000,000次運(yùn)算。我們需要更高效的解法。2.2 哈希表優(yōu)化思路關(guān)鍵觀察可以將問題拆分為兩部分先計(jì)算nums1和nums2的所有可能和再在nums3和nums4中尋找對(duì)應(yīng)的補(bǔ)數(shù)。具體步驟遍歷nums1和nums2計(jì)算所有ab的和并用哈希表記錄每個(gè)和出現(xiàn)的次數(shù)遍歷nums3和nums4計(jì)算所有cd的和在哈希表中查找-(cd)的計(jì)數(shù)將所有匹配的計(jì)數(shù)累加得到最終結(jié)果這種方法將時(shí)間復(fù)雜度降為O(n^2)空間復(fù)雜度也是O(n^2)。2.3 代碼實(shí)現(xiàn)與細(xì)節(jié)def fourSumCount(nums1, nums2, nums3, nums4): from collections import defaultdict sum_map defaultdict(int) count 0 # 計(jì)算nums1和nums2的所有和 for a in nums1: for b in nums2: sum_map[a b] 1 # 在nums3和nums4中查找補(bǔ)數(shù) for c in nums3: for d in nums4: target - (c d) count sum_map.get(target, 0) return count注意這里使用defaultdict可以避免鍵不存在的判斷但普通字典的get方法也能實(shí)現(xiàn)同樣效果。在實(shí)際面試中解釋清楚選擇理由很重要。2.4 復(fù)雜度分析與優(yōu)化空間時(shí)間復(fù)雜度O(n^2)因?yàn)槲覀冞M(jìn)行了兩次雙重循環(huán)每次都是n^2次操作。 空間復(fù)雜度O(n^2)最壞情況下nums1和nums2的所有和都不同。進(jìn)一步優(yōu)化如果某個(gè)數(shù)組有大量重復(fù)元素可以考慮先統(tǒng)計(jì)元素頻率再計(jì)算但一般情況下上述解法已經(jīng)足夠。3. 383.贖金信字符頻率統(tǒng)計(jì)3.1 問題描述與簡(jiǎn)單解法給定一個(gè)贖金信字符串和一個(gè)雜志字符串判斷贖金信是否能由雜志中的字符構(gòu)成。雜志中的每個(gè)字符只能在贖金信中使用一次。最直接的思路是用哈希表統(tǒng)計(jì)雜志中字符的頻率然后檢查贖金信的字符是否都能滿足。3.2 實(shí)現(xiàn)細(xì)節(jié)與邊界條件def canConstruct(ransomNote, magazine): from collections import defaultdict mag_count defaultdict(int) # 統(tǒng)計(jì)雜志字符頻率 for c in magazine: mag_count[c] 1 # 檢查贖金信 for c in ransomNote: mag_count[c] - 1 if mag_count[c] 0: return False return True提示在Python中可以使用Counter更簡(jiǎn)潔地實(shí)現(xiàn)但手動(dòng)實(shí)現(xiàn)能更好地展示理解深度。3.3 空間優(yōu)化與替代方案如果字符集有限如僅小寫字母可以用固定大小的數(shù)組代替哈希表def canConstruct(ransomNote, magazine): count [0] * 26 for c in magazine: count[ord(c) - ord(a)] 1 for c in ransomNote: count[ord(c) - ord(a)] - 1 if count[ord(c) - ord(a)] 0: return False return True這種方法空間復(fù)雜度為O(1)固定26個(gè)位置在實(shí)際應(yīng)用中效率更高。4. 15.三數(shù)之和雙指針經(jīng)典應(yīng)用4.1 問題難點(diǎn)與暴力解法局限給定整數(shù)數(shù)組nums返回所有不重復(fù)的三元組[nums[i], nums[j], nums[k]]使得i≠j≠k且nums[i]nums[j]nums[k]0。暴力三重循環(huán)的O(n^3)解法不僅效率低還需要處理重復(fù)結(jié)果。我們需要更聰明的辦法。4.2 排序加雙指針解法關(guān)鍵步驟對(duì)數(shù)組排序O(nlogn)固定一個(gè)數(shù)nums[i]然后在i1到末尾的區(qū)間內(nèi)使用雙指針尋找兩數(shù)之和等于-nums[i]跳過重復(fù)元素以避免重復(fù)解def threeSum(nums): nums.sort() res [] n len(nums) for i in range(n - 2): # 跳過重復(fù)的nums[i] if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 target -nums[i] while left right: s nums[left] nums[right] if s target: res.append([nums[i], nums[left], nums[right]]) # 跳過重復(fù)元素 while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif s target: left 1 else: right - 1 return res4.3 復(fù)雜度分析與注意事項(xiàng)時(shí)間復(fù)雜度O(n^2) - 外層循環(huán)O(n)內(nèi)層雙指針O(n) 空間復(fù)雜度O(1)或O(n)取決于排序?qū)崿F(xiàn)關(guān)鍵細(xì)節(jié)必須先排序數(shù)組需要仔細(xì)處理重復(fù)元素雙指針移動(dòng)時(shí)要注意邊界條件5. 18.四數(shù)之和三數(shù)之和的擴(kuò)展5.1 問題升級(jí)與解法思路在15題基礎(chǔ)上現(xiàn)在要求找出所有不重復(fù)的四元組使得四數(shù)之和等于目標(biāo)值本題中目標(biāo)值固定為0但解法可推廣。解法思路類似三數(shù)之和增加一層循環(huán)排序數(shù)組固定兩個(gè)數(shù)nums[i]和nums[j]在j1到末尾區(qū)間使用雙指針尋找兩數(shù)之和等于target-nums[i]-nums[j]5.2 代碼實(shí)現(xiàn)與剪枝優(yōu)化def fourSum(nums, target): nums.sort() res [] n len(nums) for i in range(n - 3): # 跳過重復(fù)的nums[i] if i 0 and nums[i] nums[i - 1]: continue # 剪枝最小和已經(jīng)大于target if nums[i] nums[i1] nums[i2] nums[i3] target: break # 剪枝最大和仍然小于target if nums[i] nums[n-3] nums[n-2] nums[n-1] target: continue for j in range(i 1, n - 2): # 跳過重復(fù)的nums[j] if j i 1 and nums[j] nums[j - 1]: continue # 類似的剪枝優(yōu)化 if nums[i] nums[j] nums[j1] nums[j2] target: break if nums[i] nums[j] nums[n-2] nums[n-1] target: continue left, right j 1, n - 1 current_target target - nums[i] - nums[j] while left right: s nums[left] nums[right] if s current_target: res.append([nums[i], nums[j], nums[left], nums[right]]) # 跳過重復(fù)元素 while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif s current_target: left 1 else: right - 1 return res5.3 性能優(yōu)化與邊界處理添加了多級(jí)剪枝條件提前終止不可能產(chǎn)生解的分支注意處理大整數(shù)溢出的情況Python中不需要特別處理但其他語言可能需要時(shí)間復(fù)雜度O(n^3)但通過剪枝在實(shí)際運(yùn)行中可能接近O(n^2)6. 算法技巧總結(jié)與實(shí)戰(zhàn)建議6.1 哈希表與雙指針的選擇哈希表適合需要快速查找的場(chǎng)景不要求順序或位置關(guān)系需要統(tǒng)計(jì)頻率或存在性雙指針適合已排序數(shù)組需要利用元素間大小關(guān)系需要減少時(shí)間復(fù)雜度如從O(n^2)降到O(n)6.2 處理重復(fù)元素的通用方法先排序數(shù)組在循環(huán)中檢查當(dāng)前元素是否與前一個(gè)相同找到解后跳過所有連續(xù)相同元素6.3 面試中的常見錯(cuò)誤忘記處理重復(fù)元素雙指針移動(dòng)邏輯錯(cuò)誤該移動(dòng)左指針時(shí)移動(dòng)了右指針邊界條件處理不當(dāng)如數(shù)組長(zhǎng)度不足過早優(yōu)化如在不必要時(shí)添加剪枝6.4 個(gè)人刷題心得在實(shí)際刷題中我發(fā)現(xiàn)這類問題有幾個(gè)關(guān)鍵點(diǎn)先寫出暴力解法再思考優(yōu)化方向畫圖輔助理解雙指針的移動(dòng)邏輯對(duì)于重復(fù)元素處理可以用小規(guī)模測(cè)試用例驗(yàn)證在面試中要邊寫邊解釋思考過程