????????工作做多了有時候需要回歸本心，認真刷題記憶一下算法。那就用我這練習時長兩年半的代碼農民工來嘗試著快速解析LeetCode 100吧

快速解析

哈希

?1. 兩數之和 - 力扣（LeetCode）

這題很簡單啊，思路也很多

1. 暴力搜索，復雜度 N^2

2. 排序后雙指針 復雜度 NlogN

3. 用Hash表，已經遍歷過的放入Hash表內記錄，看看跟未遍歷的求和是不是等于目標，復雜度N

func twoSum(nums []int, target int) []int {hashTable := map[int]int{}for i, x := range nums {if p, ok := hashTable[target-x]; ok {return []int{p, i}}hashTable[x] = i}return nil
}

49. 字母異位詞分組 - 力扣（LeetCode）

異位詞，比如 "abc"和"cba"，或者 "acb"，反正出現過同樣次數的都算是異位詞，那么就得想辦法，設置一個hash映射，讓他們得到的值相等。

1. 先對這個按順序排序，再拼接起來作為key

2. 整一個26長度數組，統計每個英文字母出現的次數。整個數組作為key用來記錄。

128. 最長連續序列 - 力扣（LeetCode）

用哈希直接記錄一下整個數組，這樣可以去重，還可以以O1的代價來訪問值是否存在

然后比如對于值val，如果val-1也在哈希表里，就不計算了（剪枝，降低復雜度）。如果val - 1 不再哈希表里，那么證明val是起點，不斷記錄val + 1，看看最長能夠到多少

func longestConsecutive(nums []int) int {if len(nums) == 0{return 0}cnt := map[int]bool{}for _, v := range nums{cnt[v] = true   }ans := 1for k := range cnt{if cnt[k - 1]{continue}next := k + 1for cnt[next]{next ++ans = max(ans, next - k)}}return ans
}

雙指針

283. 移動零 - 力扣（LeetCode）

這題我覺得不應該是easy，高低得是個Middle，我們可以使用雙指針，一個指針用來按順序，另一個用來遍歷非零的元素，如果遍歷到非零元素，就和第一個指針互換位置。相當于就是把非零的元素全部按順序填上，那么剩下的就都是0了，因為0會一直被置換到后面，一直往后推。

func moveZeroes(nums []int)  {for i, j := 0, 0; i < len(nums); i++{if nums[i] != 0{nums[i], nums[j] = nums[j], nums[i]j++}}    
}

11. 盛最多水的容器 - 力扣（LeetCode）

傳統的雙指針，面積是寬度×高度，寬度可以直接用減法，高度就是兩邊柱子里面最低的。

那么怎么雙指針呢，一左一右。那怎么移動指針呢？那就得嘗試往更高地方向走，我們先從最矮的一遍移動，每次求max面積，這樣就可以求出最多水的容器了。

func maxArea(height []int) int {ans := 0for i, j := 0, len(height) - 1; i < j; {area := (j - i) * min(height[i], height[j])ans = max(area, ans)if height[i] < height[j]{i ++}else{j --}}    return ans
}

15. 三數之和 - 力扣（LeetCode）

正常情況之下，我們是不是想要用3個for，這樣就是N^3。一般這時候就會想著省時間了，排序，或者二分。因為這里是找3個數，所以先要排序，排序完后就是一個有順序的數組。

我們用一層循環來遍歷第一個數，剩下的復雜度實際上就是兩數之和的復雜度了。

這個兩數之和，我們可以用雙指針，不斷地往中間夾縮小范圍。這樣時間復雜度就小于On了。

func threeSum(nums []int) (ans [][]int) {sort.Ints(nums)n := len(nums)for i := 0; i < n - 2; i ++{if i > 0 && nums[i] == nums[i-1]{continue}j, k := i + 1, n - 1 target := -nums[i]for j < k{        sum := nums[j] + nums[k]if  sum == target{ans = append(ans, []int{nums[i], nums[j], nums[k]})for j < k && nums[j] == nums[j+1]{j++}for j < k && nums[k] == nums[k-1]{k--}j++k--}else if sum < target{j++}else{k--}}}return
}

42. 接雨水 - 力扣（LeetCode）

這題是比較簡單的2D接雨水，跟11題非常像，但是又不一樣，因為第11題的柱子不占空間，這一題的方塊占空間。

我們可以很明顯地看到，對于第i個位置可以儲藏的雨水，肯定是 min(left, right) - val[i]的，所以我們需要計算左邊和右邊的高度的最大值，然后再往中間逼近，每一列儲存的雨水需要每一步一步慢慢計算累加。

func trap(height []int) int {i, j := 0, len(height) - 1leftMax, rightMax := 0, 0ans := 0for i < j{leftMax = max(leftMax, height[i])rightMax = max(rightMax, height[j])if leftMax < rightMax{           ans += leftMax - height[i]            i ++}else{ans += rightMax - height[j]j--}}return ans
}

滑動窗口

3. 無重復字符的最長子串 - 力扣（LeetCode）

維護一個哈希表，如果元素沒有在哈希表里，就加進去。如果元素已經在哈希表里了，那么證明此時已經是最大的了，記錄一下，左邊窗口收縮到符合條件，右邊窗口再擴張，不斷地調整滑動窗口的大小。

func lengthOfLongestSubstring(s string) int {hash := map[byte]int{}ans := 0startIndex := 0for i := 0; i < len(s); i ++{for hash[s[i]] > 0{x := s[startIndex]startIndex++delete(hash, x)}       hash[s[i]]++ans = max(ans, len(hash))}return ans
}

438. 找到字符串中所有字母異位詞 - 力扣（LeetCode）

其實有點類似第49題的。甚至更簡單，這邊快速寫了個go版本，可以參考下
?

func findAnagrams(s string, p string) []int {hash := map[[26]int]bool{}arr := [26]int{}for i := range p{arr[p[i] - 'a'] ++}hash[arr] = truenewArr := [26]int{}pLen := len(p)ans := []int{}for i := 0; i < len(s); i++{newArr[s[i] - 'a'] ++if i >= pLen{newArr[s[i - pLen] - 'a']--}if hash[newArr]{ans = append(ans, i - pLen + 1)}}return ans
}

子串

560. 和為 K 的子數組 - 力扣（LeetCode）

這邊的子數組是要連續的，最基礎的就是暴力啊，確定一個起點，一個終點。

其實可以認為是雙指針，也可以認為是滑動數組。具體的做法也是這樣的。如果這個題目的數組值都是正數就很好優化。不過因為可能存在負數，所以我們只能想辦法通過空間換時間。就用前綴和吧。具體怎么做呢，可以參考two-sum，把前綴和放到hash里面，然后如果差值存在的話，就有一種情況了，示例代碼如下：

func subarraySum(nums []int, k int) int {cnt, pre := 0, 0m := map[int]int{}m[0] = 1for _, v := range nums{pre += vif m[pre - k] > 0{cnt += m[pre - k]}m[pre] ++}return cnt
}

239. 滑動窗口最大值 - 力扣（LeetCode）

先看一眼，優先隊列。但是除了python以外，每個語言的優先隊列好像都不太好寫。最近在寫go，寫起來還要自己構造struct，實現interface，因此再看一眼，其實可以按照遞減順序來記錄的，但是這里面最好記錄的是nums數組的index，這樣子才號刪除掉。

func maxSlidingWindow(nums []int, k int) []int {arr := []int{}push := func(i int){for len(arr) > 0 && nums[i] >= nums[arr[len(arr) - 1]]{arr = arr[:len(arr) - 1]}arr = append(arr, i)}for i := 0; i < k; i++{push(i)}n := len(nums)ans := make([]int, 1, n - k + 1)ans[0] = nums[arr[0]]for i := k; i < n; i++{push(i);for arr[0] <= i-k{arr = arr[1:]}ans = append(ans, nums[arr[0]])}return ans
}

76. 最小覆蓋子串 - 力扣（LeetCode）

滑動窗口把，或者雙指針，實際上都是一個東西。

func minWindow(s string, t string) (ans string) {cnt := make([]int, 128)// less 記錄還有幾個沒有滿足的字符less := 0for _, ch := range t {if cnt[ch] == 0 {less++}cnt[ch]++}l := 0for r, ch := range s {cnt[ch]--if cnt[ch] == 0 {less--}for less == 0 {if len(ans) == 0 || r-l < len(ans) {ans = s[l : r+1]}if cnt[s[l]] == 0 {less++}cnt[s[l]]++l++}}return
}

普通數組

53. 最大子數組和 - 力扣（LeetCode）

這題直接貪心，從左到右遍歷累加，，如果累加起來小于0，那就干脆前面的直接丟棄掉。重新累加。

func maxSubArray(nums []int) int {ans := nums[0]sum := 0for _, v := range nums{sum += vans = max(ans, sum)if sum < 0{sum = 0}}return ans
}