两数之和

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}
}// 仅使用常数空间的一趟扫描算法

下一个排列

寻找重复数