前置知识：哈希表的用法
对输入数据进行预处理是一个很重要的技巧，构建前缀信息正是其中之一
解决如下问题，时间复杂度
题目1.子数组范围求和问题
构建前缀和数组，快速解决子数组范围求和的问题
题目描述
给定一个整数数组 nums，处理以下类型的多个查询：计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的 和 ，其中 left <= right
实现 NumArray 类：
NumArray(int[] nums)使用数组nums初始化对象int sumRange(int i, int j)返回数组nums中索引left和right之间的元素的 总和 ，包含left和right两点（也就是nums[left] + nums[left + 1] + ... + nums[right])
测试链接
答案
type NumArray []int
func Constructor(nums []int) NumArray {
// 前缀和数组：sum[i] 表示 nums[:i] 的和
// 最前面加一个 0，为了省去 left = 0 时的边界讨论
// 不加的话可以在原数组上累加，省了 O(n) 的空间复杂度
// 但是需要边界讨论，更重要的是修改了原数组，构造函数不应该修改传入的参数
sum := make([]int, len(nums)+1)
for i, num := range nums {
sum[i+1] = sum[i] + num
}
return NumArray(sum)
}
func (this NumArray) SumRange(left int, right int) int {
return this[right+1] - this[left]
}
/**
* Your NumArray object will be instantiated and called as such:
* obj := Constructor(nums);
* param_1 := obj.SumRange(left,right);
*/题目2.无序数组中累加和为给定值的最长子数组长度
构建前缀和最早出现的位置，返回无序数组中累加和为给定值的最长子数组长度
题目描述
给定一个无序数组 arr, 其中元素可正、可负、可 0。给定一个整数 k，求 arr 所有子数组中累加和为 k 的最长子数组长度
测试链接
答案
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
const (
MAXN = 1e5
)
var (
arr = [MAXN]int{}
n int
k int
mp map[int]int // 0-key 的前缀和最早出现在 val 索引处
)
func main() {
in := bufio.NewScanner(os.Stdin)
in.Split(bufio.ScanWords)
out := bufio.NewWriterSize(os.Stdout, 4096)
for in.Scan() {
n, _ = strconv.Atoi(in.Text())
in.Scan()
k, _ = strconv.Atoi(in.Text())
for i := 0; i < n; i++ {
in.Scan()
arr[i], _ = strconv.Atoi(in.Text())
}
// 牛客 go 版本太低，没有 clear 方法，只能重新建一个了
// clear(mp)
mp = map[int]int{}
fmt.Fprintln(out, compute())
}
out.Flush()
}
func compute() int {
ans := 0
sum := 0
// 重要: 0 这个前缀和，一个数字也没有的时候，就存在了
mp[0] = -1
for i := 0; i < n; i++ {
sum += arr[i]
if idx, has := mp[sum-k]; has {
if i-idx > ans {
ans = i - idx
}
}
// 因为求最长，所有要记录最早出现的索引
if _, has := mp[sum]; !has {
mp[sum] = i
}
}
return ans
}题目3.无序数组中累加和为给定值的子数组数量
构建前缀和出现的次数，返回无序数组中累加和为给定值的子数组数量
题目描述
给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数
子数组是数组中元素的连续非空序列。
测试链接
答案
func subarraySum(nums []int, k int) int {
ans := 0
// 0 这个前缀和，在没有任何数字的时候，已经有1次了
mp := map[int]int{0: 1}
sum := 0
for _, num := range nums {
sum += num
if count, has := mp[sum-k]; has {
ans += count
}
mp[sum]++
}
return ans
}题目4.无序数组中正数和负数个数相等的最长子数组长度
构建前缀和最早出现的位置，返回无序数组中正数和负数个数相等的最长子数组长度
题目描述
给定一个无序数组 arr，其中元素可正、可负、可 0。求 arr 所有子数组中正数与负数个数相等的最长子数组的长度
要求：时间复杂度 ，空间复杂度为
测试链接
思路
同 题目2，将正数看成 1，负数看成 -1，零还是 0
答案
package main
import (
"bufio"
"fmt"
"os"
"strconv"
)
const (
MAXN = 1e5
)
var (
arr = [MAXN]int{}
n int
mp map[int]int
)
func main() {
in := bufio.NewScanner(os.Stdin)
in.Split(bufio.ScanWords)
out := bufio.NewWriterSize(os.Stdout, 4096)
for in.Scan() {
n, _ = strconv.Atoi(in.Text())
if n <= 0 {
continue
}
for i := 0; i < n; i++ {
in.Scan()
arr[i], _ = strconv.Atoi(in.Text())
}
// 牛客 go 版本太低，没有 clear 方法，只能重新建一个了
// clear(mp)
mp = map[int]int{}
fmt.Fprintln(out, compute())
}
out.Flush()
}
func compute() int {
ans := 0
sum := 0
mp[0] = -1
for i := 0; i < n; i++ {
if arr[i] > 0 {
sum++
} else if arr[i] < 0 {
sum--
}
if idx, has := mp[sum]; has {
if i-idx > ans {
ans = i - idx
}
} else {
mp[sum] = i
}
}
return ans
}题目5.表现良好的最长时间段问题
构建前缀和最早出现的位置，解决表现良好的最长时间段问题
题目描述
给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」
请你返回「表现良好时间段」的最大长度
测试链接
思路
同 题目2，将大于 8 看成 1，小于等于 8 看成 -1，题目转换为求子数组累加和大于等于 1 的最大长度
答案
func longestWPI(hours []int) int {
ans := 0
sum := 0
mp := map[int]int{0: -1}
for i, hour := range hours {
if hour > 8 {
sum++
} else {
sum--
}
if sum > 0 {
ans = i + 1
} else if idx, has := mp[sum-1]; has {
// sum 只能递增或递减，所以走到这里代表 sum == 0
// 所以用 mp[sum-1]
if i-idx > ans {
ans = i - idx
}
}
if _, has := mp[sum]; !has {
mp[sum] = i
}
}
return ans
}题目6.使数组和能被 P 整除
构建前缀和余数最晚出现的位置。移除的最短子数组长度，使得剩余元素的累加和能被 p 整除
题目描述
给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。
请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。
子数组 定义为原数组中连续的一组元素。
测试链接
思路
前缀信息是一个 map，key 是 前缀和 % p 的余数，value 是最晚出现的位置
求出 数组累加和 % p 的余数记为 mod，然后遍历数组来到每个位置 i，求以 i 结尾的 子数组累加和 % p 的余数等于 mod 的最小长度
怎么求？
记 0~i 的前缀和 % p 的余数为 cur
- 如果
cur >= mod：在map中找cur - mod最晚出现的位置 - 如果
cur < mod：在map中找cur + p - mod最晚出现的位置
上面两个式子可以统一写成 (cur - mod + p) % p（减法同余原理）
答案
func minSubarray(nums []int, p int) int {
// 整体余数
mod := 0
for _, num := range nums {
mod = (mod + num) % p // 加法同余原理
}
if mod == 0 {
// 数组已经能被 p 整除，移除 0 长度子数组
return 0
}
n := len(nums)
ans := n // math.MaxInt
// key: 前缀和 % p 的余数
// value: 最晚出现的位置
mp := map[int]int{0: -1}
cur := 0
for i, num := range nums {
// 0~i 的余数
cur = (cur + num) % p
// 减法同余原理
find := (cur - mod + p) % p
// 等价于：
// find := cur - mod
// if cur < mod {
// find = cur + p - mod
// }
if idx, has := mp[find]; has {
if i-idx < ans {
ans = i - idx
}
}
// 最晚出现位置，每次都更新
mp[cur] = i
}
if ans == n {
return -1
}
return ans
}题目7.每个元音包含偶数次的最长子串长度
构建前缀奇偶状态最早出现的位置
题目描述
给你一个字符串 s ，请你返回满足以下条件的最长子字符串的长度：每个元音字母，即 'a'，'e'，'i'，'o'，'u'，在子字符串中都恰好出现了偶数次
测试链接
答案
func findTheLongestSubstring(s string) int {
n := len(s)
ans := 0
// 只有 5 个元音字符，状态就 5 位：0b00000~0b11111，共 2^5 = 32 个
// 数据量较小且连续的情况下，用数组代替哈希表
mp := [32]int{}
// 因为用数组代替哈希表，没有是否存在的 API
// 所以用 -2 代表没出现过
for i := range mp {
mp[i] = -2
}
mp[0] = -1
// 位状态：代表元音字符出现的奇偶性
status := 0
for i := 0; i < n; i++ {
// status: 0~i 的元音字符出现奇偶性位状态
setStatus(&status, s[i])
// 就找 status，因为：奇+奇=偶，偶+偶=偶
if mp[status] != -2 {
ans = max(ans, i-mp[status])
} else {
// 求最长，存最左位置
mp[status] = i
}
}
return ans
}
func setStatus(status *int, char byte) {
bit := -1
switch char {
case 'a':
bit = 0
case 'e':
bit = 1
case 'i':
bit = 2
case 'o':
bit = 3
case 'u':
bit = 4
}
if bit != -1 {
// 奇变偶，偶变奇
*status ^= 1 << bit
}
}备注
构建某个前缀信息：最早出现、最晚出现、出现次数等，是很常见的技巧
除此之外，还有很多种类的前缀信息可以构建出来，解决很多子数组相关问题
更多题目会在题目系列里见到