兩數之和

func twoSum(nums []int, target int) []int {m := make(map[int]int, 0)for i := 0; i < len(nums); i++ {if _, exist := m[target-nums[i]]; exist {return []int{i, m[target-nums[i]]}} else {m[nums[i]] = i}}return []int{}
}

字母異位詞分組

func groupAnagrams(strs []string) [][]string {m := make(map[string][]string)for _, str := range strs {count := make([]int, 26)for i := 0; i < len(str); i++ {count[str[i]-'a']++}// 把 count 序列化成 keykey := ""for i, c := range count {if c > 0 {// []byte can not use as map's key, use word+num insteadkey += string('a'+i) + strconv.Itoa(c)}}m[key] = append(m[key], str)}result := make([][]string, 0, len(m))for _, v := range m {result = append(result, v)}return result
}func groupAnagrams(strs []string) [][]string {// 在 Go 里，數組是值類型，不是引用類型mp := map[[26]int][]string{}for _, str := range strs {cnt := [26]int{}for _, b := range str {cnt[b-'a']++}mp[cnt] = append(mp[cnt], str)}ans := make([][]string, 0, len(mp))for _, v := range mp {ans = append(ans, v)}return ans
}

最長連續序列

func longestConsecutive(nums []int) int {m := make(map[int]bool)for _, v := range nums {m[v] = true}longest := 0// using map can avoid large number of redundant comparisonsfor v := range m {// 判斷當前數字是不是 "序列起點"，這招超萬能// 很多 LeetCode 連續區間題目都能套用這個模板// 稀疏矩陣的時候，可以遍歷原map（注意不是原數組，不然重復判斷的情況仍會存在）// 找到比這個數小不在map里，這個數就看作是起點，不斷找到比他大的數在不在map中，就能少了很多無效判斷if !m[v-1] {length := 1n := vfor m[n+1] {n++length++}if length > longest {longest = length}}}return longest
}

移動零

func moveZeroes(nums []int) {// 雙指針的思路，做的時候容易過分重視 i 和 j 指針// i 指針是指向非零元素應該放入的位置，而 j 指針應該去尋找非零元素把其放入 i 指針所指向的位置，一次遍歷// index at i is the num not equal to zero// index at j is the num equal to zero// i for storing the num not zero, j for scanningleft, right, n := 0, 0, len(nums)for right < n {if nums[right] != 0 {nums[left], nums[right] = nums[right], nums[left]left++}right++}
}
// 另一思路：把所有非零元素左移，后面全填充 0

盛水最多的容器

// 貪心，比當前指針大的才需要移動
// 為什么移動較低指針是正確的？
// 因為當前最大的盛水量是由寬度和最短板高度決定的，如果移動較長的板，無論是高了還是矮了，最大盛水量都是由短的木板來決定，但是寬度已經減少了，所以移動較長的木板并不會使我們的盛水容量增加
// 但是移動短的木板，雖然我們的寬度減少了，但是由于木板可能會變長，所以我們的盛水容量可能會變大，所以移動短的木板才是正確的
func maxArea(height []int) int {max := 0i, j := 0, len(height)-1for i < j {area := (j - i) * min(height[i], height[j])if area > max {max = area}// if move the higher, area must be smaller, because the area depends on the shorter side// but if move the shorter, area may be largerif height[i] <= height[j] {i++} else {j--}}return max
}

三數之和

func threeSum(nums []int) [][]int {l := len(nums)result := make([][]int, 0)sort.Ints(nums)// pay attention to the loop termination conditionfor i := 0; i < l-2; i++ {// deduplicationif i > 0 && nums[i] == nums[i-1] {continue}left, right := i+1, l-1for left < right {sum := nums[i] + nums[left] + nums[right]if sum == 0 {result = append(result, []int{nums[i], nums[left], nums[right]})// skip the repeated elements on the leftfor left < right && nums[left] == nums[left+1] {left++}// skip the repeated elements on the rightfor left < right && nums[right] == nums[right-1] {right--}left++right--} else if sum < 0 {left++} else {right--}}}return result
}

接雨水

在這里插入代碼片

無重復字符的最長子串

func lengthOfLongestSubstring(s string) int {result := 0mp := make(map[byte]int)length := len(s)l := 0for i := 0; i < length; i++ {// if the index is greater than or equal to the left boundary,// it can be included in the sliding window,// thus eliminating the need to delete elements from the mapif index, exist := mp[s[i]]; exist && index >= l {l = index + 1}if result < i-l+1 {result = i - l + 1}mp[s[i]] = i}return result
}func lengthOfLongestSubstring(s string) (ans int) {cnt := [128]int{} // 也可以用 map，這里為了效率用的數組left := 0for right, c := range s {cnt[c]++for cnt[c] > 1 { // 窗口內有重復字母cnt[s[left]]-- // 移除窗口左端點字母left++ // 縮小窗口}ans = max(ans, right-left+1) // 更新窗口長度最大值}return ans
}

找到字符串中所有字母異位詞

func findAnagrams(s string, p string) []int {result := make([]int, 0)// using map is actually not very efficient// an optimization idea is to switch to array countingms, mp := make(map[byte]int), make(map[byte]int)lenp := len(p)// comparison function moved insidemapsEqual := func(a, b map[byte]int) bool {if len(a) != len(b) {return false}for k, v := range a {if bv, ok := b[k]; !ok || bv != v {return false}}return true}for i := 0; i < lenp; i++ {mp[p[i]]++}for i := 0; i < len(s); i++ {ms[s[i]]++if i < lenp-1 {continue}if mapsEqual(ms, mp) {result = append(result, i-lenp+1)}// cannot directly delete the key// if the character appears multiple times in the window, it will cause counting errors// cannot simply subtract one from the count, as the presence of a key can lead to incorrect judgments// the correct approach is to subtract 1. If it is reduced to 0, then delete:ms[s[i-lenp+1]]--if ms[s[i-lenp+1]] == 0 {delete(ms, s[i-lenp+1])}}return result
}

和為 K 的子數組

在這里插入代碼片

滑動窗口最大值

在這里插入代碼片

最小覆蓋子串

在這里插入代碼片

最大子數組和

• 這道題一開始想的思路是前綴和的做法，但是前綴和在枚舉所有連續子數組的時候時間復雜度仍然是 O($n^2$)。
• 這道題應該用動態規劃，用 nums[i] 變量記錄以 i 個數結尾的連續子數組的最大和，如果以 i-1 個數結尾的連續子數組的最大和是負數，那么只會拖累我們目前 i 這個位置的以 i 個數結尾的連續子數組的最大和，還不如自己另起爐灶，所以當 nums[i-1] < 0 時應該舍棄掉，然后記錄 nums 數組中的最大值即可。

在這里插入代碼片

合并區間

在這里插入代碼片

輪轉數組

• 很直觀的思路是額外開辟一個數組依次按新的位置復制即可，但這樣空間復雜度 O(n)。
• 想不到題解這種巧妙的方法：翻轉就是把末尾 k 個元素翻轉到數組前頭，其他元素依次后移；可以先把整個數組翻轉，這樣就做到了末尾 k 個元素翻轉到數組前頭，其他元素依次后移的結果，但是因為是翻轉所以是倒序的，所以還要對左右兩數組再進行一次翻轉。

在這里插入代碼片

除自身以外數組的乘積

• 這道題用前綴積和后綴積的思想可以解決，但是卡在了如何實現空間復雜度為 O(1) 的解法。
• 其實用 answer[i] 計算了 i 位置左邊的前綴積，只需要乘上 i 位置右邊的后綴積即是所要求的答案，這個后綴積可以用一個 R 變量來記錄，然后直接作用在 answer 數組上即可。

在這里插入代碼片

缺失的第一個正數

在這里插入代碼片

矩陣置零

// O(m+n)
func setZeroes(matrix [][]int) {row := make([]bool, len(matrix))col := make([]bool, len(matrix[0]))for i, r := range matrix {for j, v := range r {if v == 0 {row[i] = truecol[j] = true}}}for i, r := range matrix {for j := range r {if row[i] || col[j] {r[j] = 0}}}
}// O(1)
// 不用額外空間，直接把“標記”存放在矩陣的第一行和第一列
// 如果 matrix[i][j] == 0，就把：matrix[i][0] = 0（這一行需要置零）matrix[0][j] = 0（這一列需要置零）這樣，第一行和第一列相當于變成了“行/列的標記數組”
// 特殊情況：第一行和第一列自身是否要清零
// 如果本來第一行或第一列就有 0，我們在標記時會混淆，所以要 單獨記下來
// 因為我們是從（1，1）開始遍歷，標記第一行和第一列的，如果不記錄下來，那么回過頭看第一行時，我們就不知道這里的0是原來就有的0還是我們標記上的0，這樣會如果是原來的，
func setZeroes(matrix [][]int) {n, m := len(matrix), len(matrix[0])row0, col0 := false, falsefor _, v := range matrix[0] {if v == 0 {row0 = truebreak}}for _, r := range matrix {if r[0] == 0 {col0 = truebreak}}for i := 1; i < n; i++ {for j := 1; j < m; j++ {if matrix[i][j] == 0 {matrix[i][0] = 0matrix[0][j] = 0}}}for i := 1; i < n; i++ {for j := 1; j < m; j++ {if matrix[i][0] == 0 || matrix[0][j] == 0 {matrix[i][j] = 0}}}if row0 {for j := 0; j < m; j++ {matrix[0][j] = 0}}if col0 {for _, r := range matrix {r[0] = 0}}
}

螺旋矩陣

func spiralOrder(matrix [][]int) []int {row, col := len(matrix), len(matrix[0])result := make([]int, 0, row*col)direction := [][]int{{0, 1}, {1, 0}, {0, -1}, {-1, 0}} // 右、下、左、上visited := make([][]bool, row)for i := 0; i < row; i++ {visited[i] = make([]bool, col)}i, j, index := 0, 0, 0// 我們不能使用 visited[i][j] 作為循環退出條件// 因為更新 i 和 j 后可能會訪問越界// 所以用 row*col 限制循環次數來保證遍歷所有元素for k := 0; k < row*col; k++ {result = append(result, matrix[i][j])visited[i][j] = true// 計算下一個位置ni, nj := i+direction[index][0], j+direction[index][1]// 如果下一個位置越界或已訪問，則轉向if ni < 0 || ni >= row || nj < 0 || nj >= col || visited[ni][nj] {index = (index + 1) % 4}// 更新 i, j 到下一步位置i += direction[index][0]j += direction[index][1]}return result
}

旋轉圖像

搜索二維矩陣 II

相交鏈表

反轉鏈表

回文鏈表

環形鏈表

環形鏈表 II

合并兩個有序鏈表

兩數相加

刪除鏈表的倒數第 N 個結點

兩兩交換鏈表中的節點

K 個一組翻轉鏈表

隨機鏈表的復制

排序鏈表

合并 K 個升序鏈表

LRU 緩存

二叉樹的中序遍歷

二叉樹的最大深度

翻轉二叉樹

對稱二叉樹

二叉樹的直徑

二叉樹的層序遍歷

將有序數組轉換為二叉搜索樹

驗證二叉搜索樹

二叉搜索樹中第 K 小的元素

二叉樹的右視圖

二叉樹展開為鏈表

從前序與中序遍歷序列構造二叉樹

路徑總和 III

二叉樹的最近公共祖先

二叉樹中的最大路徑和

島嶼數量

腐爛的橘子

課程表

實現 Trie (前綴樹)

全排列

子集

電話號碼的字母組合

組合總和

括號生成

單詞搜索

分割回文串

N 皇后

搜索插入位置

// [left,right]
// 循環條件：for left <= right
// 循環不變式：在循環開始時，始終有：
// 搜索區間為 閉區間 [left, right]
// 如果 target 存在于數組中，它一定落在 [left, right] 里
// 如果 nums[mid] < target，則更新 left = mid + 1 → 新區間仍然是閉區間 [mid+1, right]
// 如果 nums[mid] > target，則更新 right = mid - 1 → 新區間仍然是閉區間 [left, mid-1]
// 如果 nums[mid] == target，直接返回
// 終止條件：left > right → 區間為空，此時 left 是插入位置
func searchInsert(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] == target {return mid} else if nums[mid] < target {left = mid + 1} else {right = mid - 1}}return left
}// [left,right)
// 循環條件：for left < right
// 循環不變式：在循環開始時，始終有：
// 搜索區間為 左閉右開 [left, right)
// 如果 target 存在于數組中，它一定落在 [left, right) 里
// 如果 nums[mid] < target，則更新 left = mid + 1 → 新區間 [mid+1, right)
// 如果 nums[mid] >= target，則更新 right = mid → 新區間 [left, mid)
// 終止條件：left == right → 區間為空，此時 left 恰好是插入位置，如果數組中有 target，left 會停在 target 的下標
func searchInsert(nums []int, target int) int {left, right := 0, len(nums)for left < right {mid := left + (right-left)/2if nums[mid] < target {left = mid + 1} else {right = mid}}return left
}

搜索二維矩陣

// 兩次二分：行+列
func searchMatrix(matrix [][]int, target int) bool {nums_col0 := make([]int, len(matrix))for i := 0; i < len(matrix); i++ {nums_col0[i] = matrix[i][0]}// 這里要注意了，二分查找找的是第一個 ≥ target 的索引// 存在兩種情況 > 或者 ==// 如果是 > 那不會有錯誤// 當時如果行首元素剛好 == target 就會有錯誤// 所以找target + 1的索引再 - 1 保證正確// 或者可以添加額外判斷 == 的情況row_index := searchInsert(nums_col0, target+1) - 1if row_index < 0 {return false}col_index := searchInsert(matrix[row_index], target)if col_index >= len(matrix[row_index]) || matrix[row_index][col_index] != target {return false}return true
}
// 二分查找，找到第一個 ≥ target 的索引
func searchInsert(nums []int, target int) int {left, right := 0, len(nums)for left < right {mid := left + (right-left)/2if nums[mid] < target {left = mid + 1} else {right = mid}}return left
}// 一次二分
func searchMatrix(matrix [][]int, target int) bool {if len(matrix) == 0 || len(matrix[0]) == 0 {return false}m, n := len(matrix), len(matrix[0])left, right := 0, m*n-1for left <= right {mid := left + (right-left)/2val := matrix[mid/n][mid%n]if val == target {return true} else if val < target {left = mid + 1} else {right = mid - 1}}return false
}

在排序數組中查找元素的第一個和最后一個位置

func searchRange(nums []int, target int) []int {if len(nums) == 0 {return []int{-1, -1}}left, right := searchInsert(nums, target), searchInsert(nums, target+1)-1// 注意這里會有越界問題，記得判斷if left >= len(nums) || right < 0 || nums[left] != target || nums[right] != target {return []int{-1, -1}}return []int{left, right}
}
func searchInsert(nums []int, target int) int {left, right := 0, len(nums)for left < right {mid := left + (right-left)/2if nums[mid] < target {left = mid + 1} else {right = mid}}return left
}

搜索旋轉排序數組

// 進行旋轉后數組局部有序
// 把數組對半切開，一定有一半是有序的
// 可以用這有序的一半確定 target 的位置在不在這有序的一半里面
func search(nums []int, target int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2if nums[mid] == target {return mid}if nums[left] <= nums[mid] {// 注意邊界條件，上面已經確定 nums[mid] != target 了if nums[left] <= target && nums[mid] > target {right = mid - 1} else {left = mid + 1}} else {// 注意邊界條件，上面已經確定 nums[mid] != target 了if nums[mid] < target && target <= nums[right] {left = mid + 1} else {right = mid - 1}}}return -1
}

尋找旋轉排序數組中的最小值

func findMin(nums []int) int {left, right := 0, len(nums)-1for left <= right {mid := left + (right-left)/2// 數組已經有序，返回第一個元素if nums[left] <= nums[mid] && nums[mid] <= nums[right] {return nums[left]}// 前半部分單調遞增且都大于右邊的最大值，最小值在右半邊if nums[mid] > nums[right] {left = mid + 1} else {right = mid}}return -1
}

尋找兩個正序數組的中位數

有效的括號

func isValid(s string) bool {stack := make([]byte, 0)for i := 0; i < len(s); i++ {if s[i] == '(' || s[i] == '{' || s[i] == '[' {stack = append(stack, s[i])} else if s[i] == ')' || s[i] == '}' || s[i] == ']' {if len(stack) == 0 {return false}b := stack[len(stack)-1]switch s[i] {case '}':if b == '{' {stack = stack[:len(stack)-1]} else {return false}case ']':if b == '[' {stack = stack[:len(stack)-1]} else {return false}case ')':if b == '(' {stack = stack[:len(stack)-1]} else {return false}}}}if len(stack) > 0 {return false}return true
}

最小棧

type MinStack struct {// 主棧（stack）：存儲所有元素，負責正常的棧操作（Push、Pop、Top）stack    []int// 輔助棧（minStack）：專門記錄 “對應主棧狀態下的最小值”，確保 GetMin() 能直接獲取最小值minStack []int
}func Constructor() MinStack {return MinStack{stack:    []int{},minStack: []int{math.MaxInt64},}
}func (this *MinStack) Push(val int) {this.stack = append(this.stack, val)// 相當于實時記錄主棧每個元素為棧頂時，此時棧里面的最小值if this.GetMin() < val {this.minStack = append(this.minStack, this.GetMin())} else {this.minStack = append(this.minStack, val)}
}func (this *MinStack) Pop() {this.stack = this.stack[:len(this.stack)-1]this.minStack = this.minStack[:len(this.minStack)-1]
}func (this *MinStack) Top() int {return this.stack[len(this.stack)-1]
}func (this *MinStack) GetMin() int {return this.minStack[len(this.minStack)-1]
}

字符串解碼

每日溫度

func dailyTemperatures(temperatures []int) []int {stack := make([]int, 0)stack = append(stack, 0)result := make([]int, len(temperatures))for i := 1; i < len(temperatures); i++ {// 注意這里要判斷棧是否為空，否則stack[len(stack)-1]會報錯for len(stack) > 0 && temperatures[i] > temperatures[stack[len(stack)-1]] {result[stack[len(stack)-1]] = i - stack[len(stack)-1]stack = stack[:len(stack)-1]}// 存儲的是索引值，方便后續計算距離stack = append(stack, i)}return result
}

柱狀圖中最大的矩形

數組中的第K個最大元素

前 K 個高頻元素

數據流的中位數

買賣股票的最佳時機

跳躍游戲

跳躍游戲 II

劃分字母區間

爬樓梯

楊輝三角

打家劫舍

完全平方數

零錢兌換

單詞拆分

最長遞增子序列

乘積最大子數組

分割等和子集

最長有效括號

不同路徑

最小路徑和

最長回文子串

最長公共子序列

編輯距離

只出現一次的數字

// 必須設計并實現線性時間復雜度的算法來解決此問題，且該算法只使用常量額外空間
// 大部分都是出現2次，聯想到位運算：異或（XOR）運算
// a ^ a = 0
// 0 ^ a = a
// a ^ 0 = a
func singleNumber(nums []int) int {result := 0for _, v := range nums {result ^= v}return result
}

多數元素

// 多數元素是指在數組中出現次數 大于 ? n/2 ? 的元素
// 那么排序后，不管多數元素這一段怎么放，都會覆蓋數組的中點
// 時間復雜度 O(nlogn) 空間復雜度 O(logn)
func majorityElement(nums []int) int {sort.Ints(nums)return nums[len(nums)/2]
}// Boyer-Moore 投票算法
// “同歸于盡消殺法” 
// 由于多數超過50%, 比如100個數，那么多數至少51個，剩下少數是49個
// 第一個到來的士兵，直接插上自己陣營的旗幟占領這塊高地，此時領主 winner 就是這個陣營的人，現存兵力 count = 1
// 如果新來的士兵和前一個士兵是同一陣營，則集合起來占領高地，領主不變，winner 依然是當前這個士兵所屬陣營，現存兵力 count++
// 如果新來到的士兵不是同一陣營，則前方陣營派一個士兵和它同歸于盡。 此時前方陣營兵力count --
//（即使雙方都死光，這塊高地的旗幟 winner 依然不變，因為已經沒有活著的士兵可以去換上自己的新旗幟）
// 當下一個士兵到來，發現前方陣營已經沒有兵力，新士兵就成了領主，winner 變成這個士兵所屬陣營的旗幟，現存兵力 count ++
// 就這樣各路軍閥一直以這種以一敵一同歸于盡的方式廝殺下去，直到少數陣營都死光，那么最后剩下的幾個必然屬于多數陣營，winner 就是多數陣營
//（多數陣營 51個，少數陣營只有49個，死剩下的2個就是多數陣營的人）
func majorityElement(nums []int) int {if len(nums) == 0 {panic("數組不能為空")}winner := nums[0] // 候選元素count := 1         // 當前票數for i := 1; i < len(nums); i++ {if nums[i] == winner {count++ // 同陣營士兵，票數加一} else if count == 0 {winner = nums[i] // 票數為0，換領主count = 1} else {count-- // 不同陣營士兵同歸于盡，票數減一}}return winner
}

顏色分類

func sortColors(nums []int) {red0, white1, blue2 := 0, 0, 0// 統計每個顏色的數量for _, v := range nums {if v == 0 {red0++} else if v == 1 {white1++} else if v == 2 {blue2++}}// 重寫數組for i := 0; i < red0; i++ {nums[i] = 0}for i := red0; i < red0+white1; i++ {nums[i] = 1}for i := red0 + white1; i < red0+white1+blue2; i++ {nums[i] = 2}
}// 僅使用常數空間的一趟掃描算法

下一個排列

尋找重復數