Week 7 @ 2025 算法周记【Rabin-Karp 字符匹配 + 前缀和】
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
}