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}