Week 8 @ 2025 算法周记【滑动窗口 + 前缀和】

By Bryan
  • In progress
    • 3 min

    滑动窗口

    LC 485. Max Consecutive Ones 最大连续 1 的个数

    https://leetcode.com/problems/max-consecutive-ones/description/

    解法一

    func findMaxConsecutiveOnes(nums []int) int { left, right := -1, 0 maxCount := 0 for right < len(nums) { if nums[right] == 0 { maxCount = max(maxCount, right - left - 1) left = right } right++ } maxCount = max(maxCount, right - left - 1) return maxCount }

    解法二

    func findMaxConsecutiveOnes(nums []int) int { count := 0 maxCount := 0 for _, num := range nums { if num == 1 { count++ maxCount = max(maxCount, count) } else { count = 0 } } maxCount = max(maxCount, count) return maxCount }

    LC 1004. Max Consecutive Ones III 最大连续 1 的个数 III

    https://leetcode.com/problems/max-consecutive-ones-iii/

    func longestOnes(nums []int, k int) int { left, right := 0, 0 oneCount, zeroCount := 0, 0 maxCount := 0 for right < len(nums) { if nums[right] == 0 { zeroCount++ } else { oneCount++ } right++ for left < right && zeroCount > k { if nums[left] == 0 { zeroCount-- } else { oneCount-- } left++ } maxCount = max(maxCount, oneCount + zeroCount) } return maxCount }

    LC 424. Longest Repeating Character Replacement 替换后的最长重复字符

    https://leetcode.com/problems/longest-repeating-character-replacement/description/

    func characterReplacement(s string, k int) int { charsMap := make(map[byte]int, 26) maxLength := 0 left, right := 0, 0 for right < len(s) { charsMap[s[right]]++ right++ for left < right && !isValid(charsMap, k) { charsMap[s[left]]-- left++ } maxLength = max(maxLength, right-left) } return maxLength } func isValid(charsMap map[byte]int, k int) bool { totalCount := 0 maxCount := 0 for _, c := range charsMap { totalCount += c maxCount = max(maxCount, c) } return totalCount-maxCount <= k }

    简化 isValid 判断

    func characterReplacement(s string, k int) int { charsMap := make(map[byte]int, 26) maxCharCount := 0 maxLength := 0 left, right := 0, 0 for right < len(s) { charsMap[s[right]]++ maxCharCount = max(maxCharCount, charsMap[s[right]]) right++ if left < right && right-left-maxCharCount > k { charsMap[s[left]]-- left++ } maxLength = max(maxLength, right-left) } return maxLength }

    一个扩展问题：为什么收缩左边界时不需要更新（减少）maxCharCount 可能的变化？因为 maxCharCount 被高估不会破坏窗口条件！

    前缀和+哈希表

    LC 974. 和可被 K 整除的子数组

    https://leetcode.com/problems/subarray-sums-divisible-by-k/

    func subarraysDivByK(nums []int, k int) int { total := 0 preSumReverseMap := make(map[int][]int, k) preSumReverseMap[0] = []int{-1} preSum := make([]int, len(nums)+1) for i, v := range nums { ss := (preSum[i] + v) % k if ss < 0 { ss = (ss + k) % k } preSum[i+1] = ss preSumReverseMap[ss] = append(preSumReverseMap[ss], i) } for j := range nums { candidates := preSumReverseMap[preSum[j+1]] for _, i := range candidates { if i >= j { break } total++ } } return total }

    避免二次判断

    func subarraysDivByK(nums []int, k int) int { total := 0 preSumCount := make(map[int]int, k) preSumCount[0] = 1 preSum := make([]int, len(nums)+1) for i, v := range nums { ss := (preSum[i] + v) % k if ss < 0 { ss += k } preSum[i+1] = ss total += preSumCount[ss] preSumCount[ss]++ } return total }

    LC 1124. 表现良好的最长时间段

    https://leetcode.com/problems/longest-well-performing-interval/

    func longestWPI(hours []int) int { longest := 0 preSum := make([]int, len(hours) + 1) preSumMap := make(map[int]int) for i, h := range hours { v := 0 if h > 8 { v = 1 } else { v = -1 } ss := preSum[i] + v preSum[i+1] = ss if ss > 0 { longest = i+1 } else { if preIndex, ok := preSumMap[ss-1]; ok { longest = max(longest, i - preIndex) } } if _, exists := preSumMap[ss]; !exists { preSumMap[ss] = i } } return longest }

     

    Related content