{"type":"doc","content":[{"type":"extension","attrs":{"layout":"default","extensionType":"com.atlassian.confluence.macro.core","extensionKey":"toc","parameters":{"macroParams":{"style":{"value":"none"}},"macroMetadata":{"macroId":{"value":"afc1ca19-45ac-4761-80b8-ff8f75d208e5"},"schemaVersion":{"value":"1"},"title":"Table of Contents"}},"localId":"fe53d9a2-911d-4ecd-bc6e-ba2a06178714"}},{"type":"heading","attrs":{"level":2},"content":[{"text":"滑动窗口","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 485. Max Consecutive Ones 最大连续 1 的个数","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/max-consecutive-ones/description/"}},{"text":" ","type":"text"}]},{"type":"paragraph","content":[{"text":"解法一","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func findMaxConsecutiveOnes(nums []int) int {\n left, right := -1, 0\n maxCount := 0\n for right < len(nums) {\n if nums[right] == 0 {\n maxCount = max(maxCount, right - left - 1)\n left = right\n }\n\n right++\n }\n\n maxCount = max(maxCount, right - left - 1)\n\n return maxCount\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"解法二","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func findMaxConsecutiveOnes(nums []int) int {\n count := 0\n maxCount := 0\n for _, num := range nums {\n if num == 1 {\n count++\n maxCount = max(maxCount, count)\n } else {\n count = 0\n }\n }\n maxCount = max(maxCount, count)\n\n return maxCount\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 1004. Max Consecutive Ones III 最大连续 1 的个数 III","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/max-consecutive-ones-iii/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func longestOnes(nums []int, k int) int {\n left, right := 0, 0\n oneCount, zeroCount := 0, 0\n maxCount := 0\n for right < len(nums) {\n if nums[right] == 0 {\n zeroCount++\n } else {\n oneCount++\n }\n right++\n\n for left < right && zeroCount > k {\n if nums[left] == 0 {\n zeroCount--\n } else {\n oneCount--\n }\n left++\n }\n\n maxCount = max(maxCount, oneCount + zeroCount)\n }\n \n return maxCount\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 424. Longest Repeating Character Replacement 替换后的最长重复字符","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/longest-repeating-character-replacement/description/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func characterReplacement(s string, k int) int {\n charsMap := make(map[byte]int, 26)\n\n maxLength := 0\n\n left, right := 0, 0\n for right < len(s) {\n charsMap[s[right]]++\n right++\n\n for left < right && !isValid(charsMap, k) {\n charsMap[s[left]]--\n left++\n }\n\n\n maxLength = max(maxLength, right-left)\n }\n\n return maxLength\n}\n\nfunc isValid(charsMap map[byte]int, k int) bool {\n totalCount := 0\n maxCount := 0\n for _, c := range charsMap {\n totalCount += c\n maxCount = max(maxCount, c)\n }\n\n return totalCount-maxCount <= k\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"简化 isValid 判断","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func characterReplacement(s string, k int) int {\n charsMap := make(map[byte]int, 26)\n maxCharCount := 0\n\n maxLength := 0\n\n left, right := 0, 0\n for right < len(s) {\n charsMap[s[right]]++\n maxCharCount = max(maxCharCount, charsMap[s[right]])\n right++\n\n if left < right && right-left-maxCharCount > k {\n charsMap[s[left]]--\n left++\n }\n\n\n maxLength = max(maxLength, right-left)\n }\n\n return maxLength\n}\n\n","type":"text"}]},{"type":"paragraph","marks":[{"type":"indentation","attrs":{"level":1}}],"content":[{"text":"一个扩展问题：为什么收缩左边界时不需要更新（减少）","type":"text"},{"text":"maxCharCount","type":"text","marks":[{"type":"code"}]},{"text":" 可能的变化？因为 ","type":"text"},{"text":"maxCharCount","type":"text","marks":[{"type":"code"}]},{"text":" 被高估不会破坏窗口条件！","type":"text"}]},{"type":"heading","attrs":{"level":2},"content":[{"text":"前缀和+哈希表","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 974. 和可被 K 整除的子数组","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/subarray-sums-divisible-by-k/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func subarraysDivByK(nums []int, k int) int {\n total := 0\n\n preSumReverseMap := make(map[int][]int, k)\n preSumReverseMap[0] = []int{-1}\n\n preSum := make([]int, len(nums)+1)\n for i, v := range nums {\n ss := (preSum[i] + v) % k\n if ss < 0 {\n ss = (ss + k) % k\n }\n preSum[i+1] = ss\n\n preSumReverseMap[ss] = append(preSumReverseMap[ss], i)\n }\n\n for j := range nums {\n candidates := preSumReverseMap[preSum[j+1]]\n\n for _, i := range candidates {\n if i >= j {\n break\n }\n\n total++\n }\n }\n\n return total\n}","type":"text"}]},{"type":"paragraph","content":[{"text":"避免二次判断","type":"text","marks":[{"type":"strong"}]}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func subarraysDivByK(nums []int, k int) int {\n total := 0\n\n preSumCount := make(map[int]int, k)\n preSumCount[0] = 1\n\n preSum := make([]int, len(nums)+1)\n for i, v := range nums {\n ss := (preSum[i] + v) % k\n if ss < 0 {\n ss += k\n }\n preSum[i+1] = ss\n\n total += preSumCount[ss]\n\n preSumCount[ss]++\n }\n\n return total\n}","type":"text"}]},{"type":"heading","attrs":{"level":3},"content":[{"text":"LC 1124. 表现良好的最长时间段","type":"text"}]},{"type":"paragraph","content":[{"type":"inlineCard","attrs":{"url":"https://leetcode.com/problems/longest-well-performing-interval/"}},{"text":" ","type":"text"}]},{"type":"codeBlock","attrs":{"language":"go"},"content":[{"text":"func longestWPI(hours []int) int {\n longest := 0\n\n preSum := make([]int, len(hours) + 1)\n preSumMap := make(map[int]int)\n for i, h := range hours {\n v := 0\n if h > 8 {\n v = 1\n } else {\n v = -1\n }\n\n ss := preSum[i] + v\n preSum[i+1] = ss\n\n if ss > 0 {\n longest = i+1\n } else {\n if preIndex, ok := preSumMap[ss-1]; ok {\n longest = max(longest, i - preIndex)\n }\n }\n\n\n if _, exists := preSumMap[ss]; !exists {\n preSumMap[ss] = i\n }\n }\n\n return longest\n}","type":"text"}]},{"type":"paragraph"}],"version":1}