Table of Contents
梦开始的地方
哈希
1. 两数之和
暴力枚举
func twoSum(nums []int, target int) []int { left := 0 for left < len(nums) { right := left + 1 for right < len(nums) { if nums[left] + nums[right] == target { return []int{left, right} } right++ } left++ } return []int{}}哈希表
func twoSum(nums []int, target int) []int { hashMap := make(map[int]int) for i := 0; i < len(nums); i++ { wanted := target - nums[i] if index, ok := hashMap[wanted]; ok { return []int{index, i} } hashMap[nums[i]] = i } return nil}49. 字母异位词分组
排序 哈希表
func groupAnagrams(strs []string) [][]string { var ans [][]string hashMap := make(map[string][]string)
for _, str := range strs { s := []byte(str) sort.Slice(s, func(i, j int) bool { return s[i] < s[j] }) sortedStr := string(s) hashMap[sortedStr] = append(hashMap[sortedStr], str)
} for _, part := range hashMap { ans = append(ans, part) } return ans}存字母计数向量
func groupAnagrams(strs []string) [][]string { hashMap := make(map[[26]int][]string) for _, str := range strs { cnt := [26]int{} for _, b := range str { cnt[b-'a']++ } hashMap[cnt] = append(hashMap[cnt], str) } var ans [][]string for _, v := range hashMap { ans = append(ans, v) } return ans}128. 最长连续序列
排序
func longestConsecutive(nums []int) int { sort.Slice(nums, func(i, j int) bool { return nums[i] < nums[j] }) cur := 1 maxNum := 1 if len(nums) == 0 { return 0 } if len(nums) == 1 { return 1 }
pre := nums[0] for i := 1; i < len(nums); i++ { if nums[i] == pre { continue } if nums[i] == pre + 1 { cur++ } else if nums[i] > pre + 1 { maxNum = max(cur, maxNum) cur = 1 } pre = nums[i] } return max(maxNum, cur)}官方题解没给排序,结果排序更快且内存更少,那是何意味
哈希表去重
func longestConsecutive(nums []int) int { numSet := make(map[int]bool) for _, num := range nums { numSet[num] = true } longestStreak := 0 for num := range numSet { if !numSet[num - 1] { currentNum := num currentStreak := 1 for numSet[currentNum + 1] { currentNum++ currentStreak++ } if longestStreak < currentStreak { longestStreak = currentStreak } } } return longestStreak}双指针
283. 移动零
双指针交换
func moveZeroes(nums []int) { left := 0
for right := 0; right < len(nums); right++ { if nums[right] != 0 { nums[left], nums[right] = nums[right], nums[left] left++ } }}11. 盛最多水的容器
双指针+贪心
func maxArea(height []int) int { left, right := 0, len(height) - 1 var s, ans int for left < right { s = (right - left)*min(height[left], height[right]) if s > ans { ans = s } if height[left] >= height[right] { right-- } else { left++ } } return ans}15. 三数之和
定1双指针另外两个
func threeSum(nums []int) [][]int { var ans [][]int sort.Slice(nums, func(i, j int) bool { return nums[i] <= nums[j] }) for i := 0; i < len(nums)-2; i++ { if i > 0 && nums[i - 1] == nums[i] { continue } x := nums[i] left := i + 1 right := len(nums) - 1
for left < right { y := nums[left] + nums[right] if y + x == 0 { ans = append(ans, []int{x, nums[left], nums[right]}) for nums[right] == nums[right - 1] && left < right { right-- } for nums[left] == nums[left + 1] && left < right { left++ } left++ right-- } else if y + x > 0 { right-- } else if y + x < 0 { left++ } } } return ans}可以稍微优化一点
+剪枝+语法优化
func threeSum(nums []int) [][]int { slices.Sort(nums) length := len(nums) ans := make([][]int, 0) for i, num := range nums { if num > 0 { break } if i > 0 && nums[i - 1] == num { continue } target := -num left, right := i + 1, length - 1 for left < right { sum := nums[left] + nums[right] if sum > target { right-- } else if sum < target { left++ } else { for left < right && nums[left] == nums[left + 1] { left++ } for left < right && nums[right] == nums[right - 1] { right-- } ans = append(ans, []int{num, nums[left], nums[right]}) left++ right-- } } } return ans}slices.Sort相比sort.Slice
前者为泛型排序，不用闭包性能更好
nSum
func nSum(nums []int, n int, start int, target int) [][]int { res := [][]int{} length := len(nums)
if n < 2 || length-start < n { return res }
if n == 2 { left, right := start, length-1 for left < right { sum := nums[left] + nums[right] if sum == target { res = append(res, []int{nums[left], nums[right]})
for left < right && nums[left] == nums[left+1] { left++ } for left < right && nums[right] == nums[right-1] { right-- }
left++ right-- } else if sum < target { left++ } else { right-- } } return res }
for i := start; i < length; i++ { if i > start && nums[i] == nums[i-1] { continue }
if nums[i]*n > target { break }
if nums[length-1]*n < target { break }
sub := nSum(nums, n-1, i+1, target-nums[i])
for _, arr := range sub { res = append(res, append([]int{nums[i]}, arr...)) } }
return res}42. 接雨水
长官我只会双指针
func trap(height []int) int { l := len(height) left := 0 right := l - 1 leftMax := 0 rightMax := 0 ans := 0
for left < right { leftMax = max(leftMax, height[left]) rightMax = max(rightMax, height[right]) if height[left] < height[right] { ans += leftMax - height[left] left++ } else { ans += rightMax - height[right] right-- } } return ans}滑动窗口
3. 无重复字符的最长子串
哈希+滑动窗口
func lengthOfLongestSubstring(s string) int { hashMap := make(map[byte]bool) left := 0 maxLen := 0
for right := 0; right < len(s); right++ { for hashMap[s[right]] { delete(hashMap, s[left]) left++ } hashMap[s[right]] = true if right - left + 1 > maxLen { maxLen = right - left + 1 } } return maxLen}4ms
+写法优化
func lengthOfLongestSubstring(s string) int { res, left := 0, 0 cnt := [128]int{} for right := 0; right < len(s); right++ { cnt[s[right]]++ for cnt[s[right]] >= 2 { cnt[s[left]]-- left++ } res = max(res, right-left+1) } return res}0ms
438. 找到字符串中所有字母异位词
定长窗口 26字母
func findAnagrams(s string, p string) []int { sLen, pLen := len(s), len(p) if sLen < pLen { return []int{} } ans := []int{} var sCount, pCount [26]int for i, ch := range p { sCount[s[i]-'a']++ pCount[ch-'a']++ } if pCount == sCount { ans = append(ans, 0) }
for i, ch := range s[:sLen - pLen] { sCount[ch-'a']-- sCount[s[i+pLen]-'a']++ if sCount == pCount { ans = append(ans, i + 1) } } return ans}子串
560. 和为 K 的子数组
暴力+前缀和
func subarraySum(nums []int, k int) int { n := len(nums) sum := make([]int, n+1)
for i := 0; i < n; i++ { sum[i+1] = sum[i] + nums[i] }
ans := 0 for i := 0; i < n; i++ { for j := i; j < n; j++ { if sum[j+1]-sum[i] == k { ans++ } } } return ans}哈希表+前缀和
func subarraySum(nums []int, k int) int { count := 0 prefix := 0 m := map[int]int{0: 1}
for _, num := range nums { prefix += num if v, ok := m[prefix-k]; ok { count += v } m[prefix]++ } return count}239. 滑动窗口最大值
双端队列
func maxSlidingWindow(nums []int, k int) []int { n := len(nums) var ans []int deque := []int{} for i := 0; i < n; i++ { if len(deque) > 0 && deque[0] < i-k+1 { deque = deque[1:] } for len(deque) > 0 && nums[deque[len(deque)-1]] < nums[i] { deque = deque[:len(deque)-1] } deque = append(deque, i) if i >= k-1 { ans = append(ans, nums[deque[0]]) } } return ans}但这样写没有这个写法快
func maxSlidingWindow(nums []int, k int) []int { if len(nums) == 0 || k == 0 { return []int{} }
n := len(nums) result := make([]int, 0, n - k + 1) deque := make([]int, 0 , k)
for i := 0; i < n; i++ { if len(deque) > 0 && deque[0] < i - k + 1 { deque = deque[1:] }
for len(deque) > 0 && nums[deque[len(deque) - 1]] < nums[i] { deque = deque[:len(deque) - 1] }
deque = append(deque, i)
if i >= k-1 { result = append(result, nums[deque[0]]) } }
return result}区别就在result := make([]int, 0, n - k + 1)和deque := make([]int, 0 , k)
就单单因为提前分配了容量
make(type, size, cap)
第一个为8ms而第二个为1ms
这不神奇吗
76. 最小覆盖子串
滑动窗口+哈希表
func minWindow(s string, t string) string { need := make(map[byte]int) window := make(map[byte]int) for i := 0; i < len(t); i++ { need[t[i]]++ }
left, count := 0, 0 start, minLen := 0, len(s)+1
for right := 0; right < len(s); right++ { c := s[right] if _, ok := need[c]; ok { window[c]++ if window[c] == need[c] { count++ } } for count == len(need) { if right-left+1 < minLen { start = left minLen = right-left+1 } d := s[left] left++ if _, ok := need[d]; ok { if window[d] == need[d] { count-- } window[d]-- } } } if minLen == len(s) + 1 { return "" } return s[start : start + minLen]}29ms
func minWindow(s string, t string) string { n, m := len(s), len(t) if n < m { return "" } var c1, c2 [60]int tot := 0 for i := 0; i < m; i++ { idx := getIdx(t[i]) if c1[idx] == 0 { tot++ } c1[idx]++ } ans := "" for i, j := 0, 0; i < n; i++ { idx1 := getIdx(s[i]) c2[idx1]++ if c2[idx1] == c1[idx1] { tot-- }
for j < i { idx2 := getIdx(s[j]) if c2[idx2] > c1[idx2] { c2[idx2]-- j++ } else { break } }
if tot == 0 { if ans == "" || len(ans) > i-j+1 { ans = s[j : i+1] } } } return ans}
func getIdx(x byte) int { if x >= 'A' && x <= 'Z' { return int(x - 'A' + 26) } return int(x - 'a')}0ms
普通数组
53. 最大子数组和
前缀和
func maxSubArray(nums []int) int { minPre := 0 curPre := 0 maxSum := nums[0] for _, x := range nums { curPre += x if curPre - minPre > maxSum { maxSum = curPre - minPre } if curPre < minPre { minPre = curPre } } return maxSum}分治
不太会，以后再说
func maxSubArray(nums []int) int { return get(nums, 0, len(nums) - 1).mSum;}
func pushUp(l, r Status) Status { iSum := l.iSum + r.iSum lSum := max(l.lSum, l.iSum + r.lSum) rSum := max(r.rSum, r.iSum + l.rSum) mSum := max(max(l.mSum, r.mSum), l.rSum + r.lSum) return Status{lSum, rSum, mSum, iSum}}
func get(nums []int, l, r int) Status { if (l == r) { return Status{nums[l], nums[l], nums[l], nums[l]} } m := (l + r) >> 1 lSub := get(nums, l, m) rSub := get(nums, m + 1, r) return pushUp(lSub, rSub)}
func max(x, y int) int { if x > y { return x } return y}
type Status struct { lSum, rSum, mSum, iSum int}56. 合并区间
一般通过写法
func merge(intervals [][]int) [][]int { var ans [][]int var left, right int sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) for i := 0; i < len(intervals); i++ { left = intervals[i][0] right = intervals[i][1] for i < len(intervals)-1 && intervals[i+1][0] <= right { right = max(intervals[i+1][1], right) i++ } ans = append(ans, []int{left, right}) } return ans}排序+原地修改
func merge(intervals [][]int) [][]int { if (len(intervals) == 1) { return intervals } sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] }) res := make([][]int, 0) res = append(res, intervals[0]) for i := 1; i < len(intervals); i++ { if (res[len(res)-1][1] >= intervals[i][0]) { res[len(res)-1][1] = max(res[len(res)-1][1], intervals[i][1]) } else { res = append(res, intervals[i]) } } return res}189. 轮转数组
3次翻转
func rotate(nums []int, k int) { k %= len(nums) reverse(nums) reverse(nums[:k]) reverse(nums[k:])}
func reverse(nums []int) { for i, n := 0, len(nums); i < n/2; i++ { nums[i], nums[n-1-i] = nums[n-1-i], nums[i] }}238. 除了自身以外数组的乘积
前缀积 后缀积
func productExceptSelf(nums []int) []int { l := len(nums) ans := make([]int, l)
ans[0] = 1 for i := 1; i < l; i++ { ans[i] = nums[i-1] * ans[i-1] }
R := 1 for i := l - 1; i >= 0; i-- { ans[i] = ans[i] * R R *= nums[i] } return ans}41. 缺失的第一个正数
原地 哈希表
func firstMissingPositive(nums []int) int { l := len(nums) for i := 0; i < l; i++ { if nums[i] <= 0 { nums[i] = l + 1 } }
for i := 0; i < l; i++ { num := abs(nums[i]) if num <= l { nums[num - 1] = -abs(nums[num - 1]) // 打标 } }
for i := 0; i < l; i++ { if nums[i] > 0 { return i + 1 } } return l + 1}
func abs(x int) int { if x < 0 { return -x } return x}矩阵
73. 矩阵置零
两标记
func setZeroes(matrix [][]int) { n, m := len(matrix), len(matrix[0]) // 第一行 第一列 提前维护 row0, col0 := false, false for _, v := range matrix[0] { if v == 0 { row0 = true break } }
for _, r := range matrix { if r[0] == 0 { col0 = true break } }
for i := 1; i < n; i++ { for j := 1; j < m; j++ { if matrix[i][j] == 0 { matrix[i][0] = 0 matrix[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 i := 0; i < n; i++ { matrix[i][0] = 0 } }}一标记
我不喜欢
没2直观
func setZeroes(matrix [][]int) { n, m := len(matrix), len(matrix[0]) col0 := false for _, r := range matrix { if r[0] == 0 { col0 = true } for j := 1; j < m; j++ { if r[j] == 0 { r[0] = 0 matrix[0][j] = 0 } } } for i := n - 1; i >= 0; i-- { for j := 1; j < m; j++ { if matrix[i][0] == 0 || matrix[0][j] == 0 { matrix[i][j] = 0 } } if col0 { matrix[i][0] = 0 } }}54. 螺旋矩阵
按逻辑遍历
func spiralOrder(matrix [][]int) []int { ans := []int{} n, m := len(matrix[0]), len(matrix) top, bottom, left, right := 0, m - 1, 0, n - 1 for top <= bottom && left <= right { // 右 for i := left; i <= right; i++ { ans = append(ans,matrix[top][i]) } top++ // 下 for i := top; i <= bottom; i++ { ans = append(ans,matrix[i][right]) } right-- // 左 if top <= bottom { for i := right; i >= left; i-- { ans = append(ans,matrix[bottom][i]) } bottom-- } // 上 if left <= right { for i := bottom; i >= top; i-- { ans = append(ans,matrix[i][left]) } left++ } } return ans}48. 旋转图像
对角线折叠 行对称
func rotate(matrix [][]int) { n := len(matrix) for i := 0; i < n; i++ { for j := i; j < n; j++ { matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j] } } for i := 0; i < n; i++ { for j := 0; j < n/2; j++ { matrix[i][j],matrix[i][n-1-j] = matrix[i][n-1-j],matrix[i][j] } }}240. 搜索二维矩阵 II
二分查找
没用过sort.SearchInts() 原来是标准的二分
func searchMatrix(matrix [][]int, target int) bool { for _, row := range matrix { i := sort.SearchInts(row, target) if i < len(row) && row[i] == target { return true } } return false}z字查找
matrix[x][y]一路走
func searchMatrix(matrix [][]int, target int) bool { m, n := len(matrix), len(matrix[0]) x, y := 0, n-1 for x < m && y >= 0 { if matrix[x][y] == target { return true } if matrix[x][y] > target { y-- } else { x++ } } return false}链表
160. 相交链表
双指针 相交
func getIntersectionNode(headA, headB *ListNode) *ListNode { if headA == nil || headB == nil { return nil } pa, pb := headA, headB for pa != pb { if pa == nil { pa = headB } else { pa = pa.Next } if pb == nil { pb = headA } else { pb = pb.Next } } return pa}206. 反转链表
维护 cur & pre
func reverseList(head *ListNode) *ListNode { if head == nil || head.Next == nil { return head } var pre *ListNode cur,next := head, head.Next for cur != nil { next = cur.Next cur.Next = pre pre = cur cur = next } return pre}234. 回文链表
遍历后转数组
func isPalindrome(head *ListNode) bool { vals := []int{} for ; head != nil; head = head.Next { vals = append(vals, head.Val) } n := len(vals) for i, v := range vals[:n/2] { if v != vals[n-1-i] { return false } } return true}中部反转 快慢指针
看得懂也不想写
func isPalindrome(head *ListNode) bool { if head == nil && head.Next == nil { return true }
slow, fast := head, head for fast.Next != nil && fast.Next.Next != nil { slow = slow.Next fast = fast.Next.Next }
var prev *ListNode cur := slow.Next for cur != nil { next := cur.Next cur.Next = prev prev = cur cur = next }
p1, p2 := prev, head for p1 != nil && p2 != nil { if p1.Val != p2.Val { return false } p1 = p1.Next p2 = p2.Next }
return true}141. 环形链表
快慢指针
func hasCycle(head *ListNode) bool { slow, fast := head, head
for fast != nil && fast.Next != nil { slow = slow.Next fast = fast.Next.Next
if slow == fast { return true } }
return false}