資訊專欄INFORMATION COLUMN
摘要：此專欄文章是對力扣上算法題目各種方法的總結和歸納整理出最重要的思路和知識重點并以思維導圖形式呈現當然也會加上我對導圖的詳解目的是為了更方便快捷的記憶和回憶算法重點不用每次都重復看題解畢竟算法不是做了一遍就能完全記住的所
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解.
目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容).
關于本專欄所有題目的目錄鏈接, 刷算法題目的順序/注意點/技巧, 以及思維導圖源文件問題請點擊此鏈接.
想進大廠, 刷算法是必不可少的, 歡迎和博主一起打卡刷力扣算法! 博主同步更新了算法視頻講解, 更易于理解, 不想看文章的 歡迎來看!
關注博主獲得題解更新的最新消息!!!
原本在整理 n數之和 系列時是沒有整理此題的, 后來在重看 三數之和 時, 發現了這樣的評論: 百度一面題目: 找三數和最接近0, 只要將此題中的target設置0即可, 所以又重新補充了此題!
本題是 三數之和 的進階版, 在思想上和 三數之和 還是很相似的: 先對數組進行排序, 之后用雙指針進行空間優化, 同時注意去重操作. 本質的思想幾乎是一樣的, 所以對本題不太理解的朋友, 可以先看完上面鏈接中的 三數之和, 再來看本題題解.
但還是有一些和 三數之和 不同的地方, 主要體現在下面的兩個方面:
在 三數之和 中只需要判斷相等這一種情況, 其他情況不需要判斷, 操作起來是非常簡便的, 而本題中每次求和之后都需要進行判斷(無論是相等, 還是大于或小于的情況)來找出最接近的數, 這大大增加需要進行判斷的工作量, 所以在代碼的寫法上也有很大的不同之處.
因為 三數之和 沒那么多的判斷情況, 所以利用了兩層for循環來遍歷, 去重的操作也比較簡單.
for first in range(n): # 需要和上一次枚舉的數不相同 if first > 0 and nums[first] == nums[first - 1]: continue ...... # 枚舉 b for second in range(first + 1, n): # 需要和上一次枚舉的數不相同 if second > first + 1 and nums[second] == nums[second - 1]: continue而本題中判斷情況比較多, 不方便使用兩重for循環(我也嘗試了使用二重循環, 但發現在去重時候非常復雜, 不適合使用此種方法), 所以采用了while語句來進行雙指針的遍歷, 這樣在去重操作上會簡便很多, 并且代碼中實現的去重方式比官方的要簡單, 而且更方便進行記憶!
if s > target: # 如果和大于 target，移動 c 對應的指針 k -= 1 # 移動到下一個不相等的元素 while j < k and nums[k] == nums[k+1]: k -= 1可以計算出每次三數之和的最大最小值和目標值進行比較, 也可以進行優化, 其實這種方法早在之前講解的 四數之和 中就已經提到了, 但每次都計算也增加了時間消耗, 在 四數之和 中還有很有優化的必要的, 但是在 三數之和 中是否也適用就要看具體的情況了!
class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: nums.sort() n = len(nums) best = 10**7 # 枚舉 a for i in range(n): # 保證和上一次枚舉的元素不相等 if i > 0 and nums[i] == nums[i - 1]: continue # 使用雙指針枚舉 b 和 c j, k = i + 1, n - 1 while j < k: s = nums[i] + nums[j] + nums[k] # 如果和為 target 直接返回答案 if s == target: return target # 根據差值的絕對值來更新答案 if abs(s - target) < abs(best - target): best = s if s > target: # 如果和大于 target，移動 c 對應的指針 k -= 1 # 移動到下一個不相等的元素 while j < k and nums[k] == nums[k+1]: k -= 1 else: # 如果和小于 target，移動 b 對應的指針 j += 1 # 移動到下一個不相等的元素 while j < k and nums[j] == nums[j-1]: j += 1 return bestclass Solution { public int threeSumClosest(int[] nums, int target) { Arrays.sort(nums); int n = nums.length; int best = 10000000; // 枚舉 a for (int i = 0; i < n; ++i) { // 保證和上一次枚舉的元素不相等 if (i > 0 && nums[i] == nums[i - 1]) { continue; } // 使用雙指針枚舉 b 和 c int j = i + 1, k = n - 1; while (j < k) { int sum = nums[i] + nums[j] + nums[k]; // 如果和為 target 直接返回答案 if (sum == target) { return target; } // 根據差值的絕對值來更新答案 if (Math.abs(sum - target) < Math.abs(best - target)) { best = sum; } if (sum > target) { // 如果和大于 target，移動 c 對應的指針 --k; // 移動到下一個不相等的元素 while (j < k && nums[k] == nums[k+1]) { --k; } } else { // 如果和小于 target，移動 b 對應的指針 ++j; // 移動到下一個不相等的元素 while (j < k && nums[j] == nums[j-1]) { ++j; } } } } return best; }}我的更多精彩文章鏈接, 歡迎查看
各種電腦/軟件/生活/音樂/動漫/電影技巧匯總(你肯定能夠找到你需要的使用技巧)
力扣算法刷題 根據思維導圖整理筆記快速記憶算法重點內容(歡迎和博主一起打卡刷題哦)
計算機專業知識 思維導圖整理
最值得收藏的 Python 全部知識點思維導圖整理, 附帶常用代碼/方法/庫/數據結構/常見錯誤/經典思想(持續更新中)
最值得收藏的 C++ 全部知識點思維導圖整理(清華大學鄭莉版), 東南大學軟件工程初試906科目
最值得收藏的 計算機網絡 全部知識點思維導圖整理(王道考研), 附帶經典5層結構中英對照和框架簡介
最值得收藏的 算法分析與設計 全部知識點思維導圖整理(北大慕課課程)
最值得收藏的 數據結構 全部知識點思維導圖整理(王道考研), 附帶經典題型整理
最值得收藏的 人工智能導論 全部知識點思維導圖整理(王萬良慕課課程)
最值得收藏的 數值分析 全部知識點思維導圖整理(東北大學慕課課程)
最值得收藏的 數字圖像處理 全部知識點思維導圖整理(武漢大學慕課課程)
紅黑樹 一張導圖解決紅黑樹全部插入和刪除問題 包含詳細操作原理 情況對比
各種常見排序算法的時間/空間復雜度 是否穩定 算法選取的情況 改進 思維導圖整理
人工智能課件 算法分析課件 Python課件 數值分析課件 機器學習課件 圖像處理課件
考研相關科目 知識點 思維導圖整理
考研經驗–東南大學軟件學院軟件工程(這些基礎課和專業課的各種坑和復習技巧你應該知道)
東南大學 軟件工程 906 數據結構 C++ 歷年真題 思維導圖整理
最值得收藏的 考研高等數學 全部知識點思維導圖整理(張宇, 湯家鳳), 附做題技巧/易錯點/知識點整理
最值得收藏的 考研線性代數 全部知識點思維導圖整理(張宇, 湯家鳳), 附帶慣用思維/做題技巧/易錯點整理
考研思修 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研近代史 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研馬原 知識點 做題技巧 同類比較 重要會議 1800易錯題 思維導圖整理
考研數學課程筆記 考研英語課程筆記 考研英語單詞詞根詞綴記憶 考研政治課程筆記
Python相關技術 知識點 思維導圖整理
Numpy常見用法全部OneNote筆記 全部筆記思維導圖整理
Pandas常見用法全部OneNote筆記 全部筆記思維導圖整理
Matplotlib常見用法全部OneNote筆記 全部筆記思維導圖整理
PyTorch常見用法全部OneNote筆記 全部筆記思維導圖整理
Scikit-Learn常見用法全部OneNote筆記 全部筆記思維導圖整理
Java相關技術/ssm框架全部筆記
科技相關 小米手機
文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。
轉載請注明本文地址：http://m.hztianpu.com/yun/123204.html
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
摘要：最接近的三數之和給定一個包括個整數的數組和一個目標值。返回這三個數的和。假定每組輸入只存在唯一答案。例如，給定數組，，，和與最接近的三個數的和為答案參考和三數之和一樣，我先用的循環，現在用的循環 LeetCode16.最接近的三數之和 JavaScript 給定一個包括 n 個整數的數組 nums 和 一個目標值 target。找出 nums 中的三個整數，使得它們的和與 target...
摘要：空間復雜度雙指針，循環數組，較小的那個先向內移動如果高的指針先移動，那肯定不如當前的面積大計算面積更新最大面積相交鏈表方法哈希表思路將鏈表存入中，第一個相同的節點就是重合的節點復雜度時間復雜度，分別是兩個鏈表的長度。 大廠算法面試之leetcode精講7.雙指針視頻教程（高效學習）:點擊學習目錄：1.開篇介紹2...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
此專欄文章是對力扣上算法題目各種方法的總結和歸納, 整理出最重要的思路和知識重點并以思維導圖形式呈現, 當然也會加上我對導圖的詳解. 目的是為了更方便快捷的記憶和回憶算法重點(不用每次都重復看題解), 畢竟算法不是做了一遍就能完全記住的. 所以本文適合已經知道解題思路和方法, 想進一步加強理解和記憶的朋友, 并不適合第一次接觸此題的朋友(可以根據題號先去力扣看看官方題解, 然后再看本文內容). 關...
閱讀 3959·2021-11-15 11:37
閱讀 3236·2021-11-12 10:36
閱讀 4799·2021-09-22 15:51
閱讀 2638·2021-08-27 16:18
閱讀 1031·2019-08-30 15:44
閱讀 2330·2019-08-30 10:58
閱讀 1935·2019-08-29 17:18
閱讀 3454·2019-08-28 18:25
