Week 7 @ 2025 算法周记【Rabin-Karp 字符匹配 + 前缀和】

By Bryan
  • In progress
    • 3 min

    Rabin-Karp 字符匹配算法

    LC 187. Repeated DNA Sequences 重复的 DNA 序列

    https://leetcode.com/problems/repeated-dna-sequences/description/

    暴力解法

    func findRepeatedDnaSequences(s string) []string { var result []string exists := make(map[string]int, len(s)) for i := 0; i <= len(s)-10; i++ { ss := s[i:i+10] exists[ss]++ if exists[ss] == 2 { result = append(result, ss) } } return result }

    滑动哈希

    func findRepeatedDnaSequences(s string) []string { var result []string exists := make(map[int]int, len(s)) v := 0 left, right := 0, 0 for right < len(s) { v = v * 4 + getV(s[right]) right++ if right - left == 10 { exists[v]++ if exists[v] == 2 { result = append(result, s[left:right]) } v -= getV(s[left]) * 262144 // 4^9 left++ } } return result } func getV(c byte) int { switch c { case 'A': return 0 case 'C': return 1 case 'G': return 2 case 'T': return 3 default: panic("unknown") } }

    前缀和+哈希表

    LC 525. Contiguous Array 连续数组

    https://leetcode.com/problems/contiguous-array/

    func findMaxLength(nums []int) int { preSum := make([]int, len(nums)) preSum[0] = transform(nums[0]) for i := 1; i < len(nums); i++ { preSum[i] = preSum[i-1] + transform(nums[i]) } // fmt.Println(preSum) preSumMap := make(map[int]int, len(preSum)) for i, v := range preSum { preSumMap[v] = i } maxL := 0 for i, v := range preSum { if v == 0 { maxL = max(maxL, i+1) } } for i, v := range preSum { j, exists := preSumMap[v] if exists { maxL = max(maxL, abs(i - j)) } } return maxL } func transform(v int) int { if v == 0 { return -1 } else { return 1 } } func abs(v int) int { if v < 0 { return -v } else { return v } }

    进一步优化前缀和（1-based index）

    func findMaxLength(nums []int) int { preSum := make([]int, len(nums)+1) for i := range nums { preSum[i+1] = preSum[i] + transform(nums[i]) } // fmt.Println(preSum) preSumMap := make(map[int]int, len(preSum)) for i, v := range preSum { preSumMap[v] = i } maxL := 0 for i, v := range preSum { j, exists := preSumMap[v] if exists { maxL = max(maxL, abs(i - j)) } } return maxL } func transform(v int) int { if v == 0 { return -1 } else { return 1 } } func abs(v int) int { if v < 0 { return -v } else { return v } }

    LC 523. 连续的子数组和

    https://leetcode.com/problems/continuous-subarray-sum/

    func checkSubarraySum(nums []int, k int) bool { preSum := make([]int, len(nums) + 1) for i := range nums { preSum[i+1] = (preSum[i] + nums[i]) % k } preSumMap := make(map[int]int, len(nums)+1) for i, v := range preSum { preSumMap[v] = i } for i, v := range preSum { j, exists := preSumMap[v] if exists && j - i >= 2 { return true } } return false }

    LC 560. 和为 K 的子数组

    https://leetcode.com/problems/subarray-sum-equals-k/

    func subarraySum(nums []int, k int) int { preSum := make([]int, len(nums)+1) for i, v := range nums { preSum[i+1] = preSum[i] + v } mm := make(map[int][]int, len(preSum)) for i, v := range preSum { mm[v] = append(mm[v], i) } count := 0 for i, v := range preSum { js, exists := mm[v + k] if exists { for _, j := range js { if j > i { count++ } } } } return count }

    简化

    func subarraySum(nums []int, k int) int { preSum := 0 count := make(map[int]int, len(nums)+1) count[0] = 1 result := 0 for _, v := range nums { preSum += v need := preSum - k result += count[need] count[preSum]++ } return result }

    Related content