LeetCode Go · 前缀和（1）

返回题库与筛选 · 收录范围与使用说明

来源与许可

题目版权归 LeetCode；题解来自 Doocs/leetcode，按 CC BY-SA 4.0 共享。补充 Go 代码来自灵茶山艾府、halfrost，保留 MIT 许可及逐题署名。本站提取 Go、调整分类及折叠排版；标注“本站整理”的 Go 解法依据题意与参考思路补写，按 CC BY-SA 4.0 共享。收录日期：2026-10-31；主题源版本：91ef8c241a5e。

本卷 30 题 · 点击题目展开，先独立思考，再查看解法。

238. 除了自身以外数组的乘积

中等1 种解法

标签：数组、前缀和

题目、示例与约束

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。

题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。

请 不要使用除法，且在 O(n) 时间复杂度内完成此题。

 

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

 

提示：

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• 输入 保证 数组 answer[i] 在  32 位 整数范围内

 

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

方法一：两次遍历 · Go 实现

思考

除自身外的乘积等于左侧积乘右侧积。若先开两个数组存前缀、后缀积，空间不是常数。

先从左往右把前缀积写入答案，再从右往左用一个变量累乘后缀并乘入答案，从而只用输出数组。

我们定义两个变量 $\mathit{\text{left}}$ 和 $\mathit{\text{right}}$，分别表示当前元素左边所有元素的乘积和右边所有元素的乘积。初始时 $\mathit{\text{left}}=1$, $\mathit{\text{right}}=1$。定义一个长度为 $n$ 的答案数组 $\mathit{\text{ans}}$。

我们先从左到右遍历数组，对于遍历到的第 $i$ 个元素，我们用 $\mathit{\text{left}}$ 更新 $\mathit{\text{ans}}[i]$，然后 $\mathit{\text{left}}$ 乘以 $\mathit{\text{nums}}[i]$。

然后，我们从右到左遍历数组，对于遍历到的第 $i$ 个元素，我们更新 $\mathit{\text{ans}}[i]$ 为 $\mathit{\text{ans}}[i]\times \mathit{\text{right}}$，然后 $\mathit{\text{right}}$ 乘以 $\mathit{\text{nums}}[i]$。

遍历结束后，返回答案数组 $\mathit{\text{ans}}$。

时间复杂度 $O(n)$，其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。忽略答案数组的空间消耗，空间复杂度 $O(1)$。

func productExceptSelf(nums []int) []int {
	n := len(nums)
	ans := make([]int, n)
	left, right := 1, 1
	for i, x := range nums {
		ans[i] = left
		left *= x
	}
	for i := n - 1; i >= 0; i-- {
		ans[i] *= right
		right *= nums[i]
	}
	return ans
}

力扣原题 · Doocs 题解来源

325. 和等于 k 的最长子数组长度 🔒

中等1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。

 

示例 1:

输入: nums = [1,-1,5,-2,3], k = 3
输出: 4 
解释: 子数组 [1, -1, 5, -2] 和等于 3，且长度最长。

示例 2:

输入: nums = [-2,-1,2,1], k = 1
输出: 2 
解释: 子数组 [-1, 2] 和等于 1，且长度最长。

 

提示：

• 1 <= nums.length <= 2 * 105
• -104 <= nums[i] <= 104
• -109 <= k <= 109

方法一：哈希表 + 前缀和 · Go 实现

思考

最长子数组和为 $k$。枚举左右端点为 $O(n^2)$。子数组和写成前缀差 $s_i-s_j=k$，即查找最早的 $s_j=s_i-k$。

哈希表记下每个前缀和首次出现的下标（含 $0\mapsto -1$）。扫到 $s$ 时若 $s-k$ 已出现，用 $i-j$ 更新最长；仅在 $s$ 未见过时写入，以保留最左端点。

我们可以用一个哈希表 $\mathit{\text{d}}$ 记录数组 $\mathit{\text{nums}}$ 中每个前缀和第一次出现的下标，初始时 $\mathit{\text{d}}[0]=-1$。另外定义一个变量 $\mathit{\text{s}}$ 记录前缀和。

接下来，遍历数组 $\mathit{\text{nums}}$，对于当前遍历到的数字 $\mathit{\text{nums}}[i]$，我们更新前缀和 $\mathit{\text{s}}=\mathit{\text{s}}+\mathit{\text{nums}}[i]$，如果 $\mathit{\text{s}}-k$ 在哈希表 $\mathit{\text{d}}$ 中存在，不妨记 $j=\mathit{\text{d}}[\mathit{\text{s}}-k]$，那么以 $\mathit{\text{nums}}[i]$ 结尾的符合条件的子数组的长度为 $i-j$，我们使用一个变量 $\mathit{\text{ans}}$ 来维护最长的符合条件的子数组的长度。然后，如果 $\mathit{\text{s}}$ 在哈希表中不存在，我们记录 $\mathit{\text{s}}$ 和对应的下标 $i$，即 $\mathit{\text{d}}[\mathit{\text{s}}]=i$，否则我们不更新 $\mathit{\text{d}}[\mathit{\text{s}}]$。需要注意的是，可能会有多个位置 $i$ 都满足 $\mathit{\text{s}}$ 的值，因此我们只记录最小的 $i$，这样就能保证子数组的长度最长。

遍历结束之后，我们返回 $\mathit{\text{ans}}$ 即可。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。

func maxSubArrayLen(nums []int, k int) (ans int) {
	d := map[int]int{0: -1}
	s := 0
	for i, x := range nums {
		s += x
		if j, ok := d[s-k]; ok && ans < i-j {
			ans = i - j
		}
		if _, ok := d[s]; !ok {
			d[s] = i
		}
	}
	return
}

力扣原题 · Doocs 题解来源

370. 区间加法 🔒

中等2 种解法

标签：数组、前缀和

题目、示例与约束

假设你有一个长度为 n 的数组，初始情况下所有的数字均为 0，你将会被给出 k​​​​​​​ 个更新的操作。

其中，每个操作会被表示为一个三元组：[startIndex, endIndex, inc]，你需要将子数组 A[startIndex ... endIndex]（包括 startIndex 和 endIndex）增加 inc。

请你返回 k 次操作后的数组。

示例:

输入: length = 5, updates = [[1,3,2],[2,4,3],[0,2,-2]]
输出: [-2,0,3,5,3]

解释:

初始状态:
[0,0,0,0,0]

进行了操作 [1,3,2] 后的状态:
[0,2,2,2,0]

进行了操作 [2,4,3] 后的状态:
[0,2,5,5,3]

进行了操作 [0,2,-2] 后的状态:
[-2,0,3,5,3]

 

提示：

• 1 <= length <= 105
• 0 <= updates.length <= 104
• 0 <= startIdxi <= endIdxi < length
• -1000 <= inci <= 1000

方法一：差分数组 · Go 实现

思考

多次区间加，最后输出数组。每次修改区间为 $O(n)$，更新次数多则偏慢。差分把区间加变成两点修改。

$d[l]+=c$、 $d[r+1]-=c$，最后前缀和还原。每个更新 $O(1)$，总线性。

差分数组模板题。

我们定义 $d$ 为差分数组。给区间 $[l,..r]$ 中的每一个数加上 $c$，那么有 $d[l]+=c$，并且 $d[r+1]-=c$。最后我们对差分数组求前缀和，即可得到原数组。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组长度。

func getModifiedArray(length int, updates [][]int) []int {
	d := make([]int, length)
	for _, e := range updates {
		l, r, c := e[0], e[1], e[2]
		d[l] += c
		if r+1 < length {
			d[r+1] -= c
		}
	}
	for i := 1; i < length; i++ {
		d[i] += d[i-1]
	}
	return d
}

方法二：树状数组 + 差分思想 · Go 实现

思考

差分数组已是线性。若改用树状数组，区间加仍写成两点更新，查询前缀即原值。渐近多一个 $\log n$，便于扩展为在线查询。

时间复杂度 $O(n\times \log n)$。

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：

1. 单点更新 update(x, delta)： 把序列 $x$ 位置的数加上一个值 $delta$；
2. 前缀和查询 query(x)：查询序列 $[1,...x]$ 区间的区间和，即位置 $x$ 的前缀和。

这两个操作的时间复杂度均为 $O(\log n)$。

type BinaryIndexedTree struct {
	n int
	c []int
}

func NewBinaryIndexedTree(n int) *BinaryIndexedTree {
	return &BinaryIndexedTree{n: n, c: make([]int, n+1)}
}

func (bit *BinaryIndexedTree) update(x, delta int) {
	for ; x <= bit.n; x += x & -x {
		bit.c[x] += delta
	}
}

func (bit *BinaryIndexedTree) query(x int) int {
	s := 0
	for ; x > 0; x -= x & -x {
		s += bit.c[x]
	}
	return s
}

func getModifiedArray(length int, updates [][]int) (ans []int) {
	bit := NewBinaryIndexedTree(length)
	for _, e := range updates {
		l, r, c := e[0], e[1], e[2]
		bit.update(l+1, c)
		bit.update(r+2, -c)
	}
	for i := 1; i <= length; i++ {
		ans = append(ans, bit.query(i))
	}
	return
}

力扣原题 · Doocs 题解来源

523. 连续的子数组和

中等1 种解法

标签：数组、哈希表、数学、前缀和、抽屉原理

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：

一个 好的子数组 是：

• 长度 至少为 2 ，且
• 子数组元素总和为 k 的倍数。

注意：

• 子数组 是数组中 连续 的部分。
• 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。

 

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

方法一：前缀和 + 哈希表 · Go 实现

思考

需要长度至少为 $2$ 且和为 $k$ 的倍数的子数组。枚举两端再求和是 $O(n^2)$，在 $n\le {10}^5$ 下过慢。

前缀和模 $k$ 相同的两个位置，其之间的子数组和能被 $k$ 整除。哈希表记下每个余数首次出现的下标；再次遇到同一余数且间隔大于 $1$ 即可返回。余数 $0$ 预置下标 $-1$，以覆盖从开头出发的合法段。

根据题目描述，如果存在两个前缀和模 $k$ 的余数相同的位置 $i$ 和 $j$（不妨设 $j<i$），那么 $\mathit{\text{nums}}[j+1..i]$ 这个子数组的和是 $k$ 的倍数。

因此，我们可以使用哈希表存储每个前缀和模 $k$ 的余数第一次出现的位置。初始时，我们在哈希表中存入一对键值对 $(0,-1)$，表示前缀和为 $0$ 的余数 $0$ 出现在位置 $-1$。

遍历数组时，我们计算当前前缀和的模 $k$ 的余数，如果当前前缀和的模 $k$ 的余数没有在哈希表中出现过，我们就将当前前缀和的模 $k$ 的余数和对应的位置存入哈希表中。否则，如果当前前缀和的模 $k$ 的余数在哈希表中已经出现过，位置为 $j$，那么我们就找到了一个满足条件的子数组 $\mathit{\text{nums}}[j+1..i]$，因此返回 $\mathit{\text{True}}$。

遍历结束后，如果没有找到满足条件的子数组，我们返回 $\mathit{\text{False}}$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $\mathit{\text{nums}}$ 的长度。

func checkSubarraySum(nums []int, k int) bool {
	d := map[int]int{0: -1}
	s := 0
	for i, x := range nums {
		s = (s + x) % k
		if _, ok := d[s]; !ok {
			d[s] = i
		} else if i-d[s] > 1 {
			return true
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

525. 连续数组

中等1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

 

示例 1：

输入：nums = [0,1]
输出：2
说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：

输入：nums = [0,1,0]
输出：2
说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

示例 3：

输入：nums = [0,1,1,1,1,1,0,0,0]
输出：6
解释：[1,1,1,0,0,0] 是具有相同数量 0 和 1 的最长连续子数组。

 

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

方法一：前缀和 + 哈希表 · Go 实现

思考

要最长的 $0$、 $1$ 个数相等的子数组。枚举两端再计数是 $O(n^2)$，在 $n\le {10}^5$ 下过慢。

把 $0$ 看成 $-1$ 后，和为 $0$ 的子数组即 $0$、 $1$ 个数相等。前缀和相同的两个位置夹出一段平衡子数组。哈希表记下每个前缀和首次出现的下标，再次遇到时用间距更新答案。 $0$ 预置为 $-1$，以覆盖从开头出发的段。

根据题目描述，我们可以将数组中的 $0$ 视作 $-1$，这样当遇到 $0$ 时，前缀和 $s$ 就会减一，当遇到 $1$ 时，前缀和 $s$ 就会加一。因此，假设前缀和 $s$ 在下标 $j$ 和 $i$ 处的值相等，其中 $j<i$，那么从下标 $j+1$ 到 $i$ 的子数组中 $0$ 和 $1$ 的数量就是相等的。

我们使用哈希表存储所有的前缀和以及它们第一次出现的下标，初始时，我们将 $0$ 的前缀和映射到 $-1$。

遍历数组，计算前缀和 $s$，如果 $s$ 已经在哈希表中，那么我们就找到了一个和为 $0$ 的子数组，其长度为 $i-d[s]$，其中 $d[s]$ 是哈希表中保存的 $s$ 第一次出现的下标。如果 $s$ 不在哈希表中，我们将 $s$ 与它的下标 $i$ 存入哈希表。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组的长度。

func findMaxLength(nums []int) int {
	d := map[int]int{0: -1}
	ans, s := 0, 0
	for i, x := range nums {
		if x == 0 {
			x = -1
		}
		s += x
		if j, ok := d[s]; ok {
			ans = max(ans, i-j)
		} else {
			d[s] = i
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

548. 将数组分割成和相等的子数组 🔒

困难1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给定一个有 n 个整数的数组 nums ，如果能找到满足以下条件的三元组  (i, j, k)  则返回 true ：

1. 0 < i, i + 1 < j, j + 1 < k < n - 1
2. 子数组 (0, i - 1) ， (i + 1, j - 1) ， (j + 1, k - 1) ， (k + 1, n - 1) 的和应该相等。

这里我们定义子数组 (l, r) 表示原数组从索引为 l 的元素开始至索引为 r 的元素。

 

示例 1: 

输入: nums = [1,2,1,2,1,2,1]
输出: True
解释:
i = 1, j = 3, k = 5. 
sum(0, i - 1) = sum(0, 0) = 1
sum(i + 1, j - 1) = sum(2, 2) = 1
sum(j + 1, k - 1) = sum(4, 4) = 1
sum(k + 1, n - 1) = sum(6, 6) = 1

示例 2:

输入: nums = [1,2,1,2,1,2,1,2]
输出: false

 

提示:

• n == nums.length
• 1 <= n <= 2000
• -106 <= nums[i] <= 106

方法一：前缀和 + 哈希表 · Go 实现

思考

要把数组切成和相等的四段，中间丢掉三个切点元素。四重枚举切点是 $O(n^4)$。

固定中间切点 $j$ 后，左侧能形成的相等两段之和放入集合，右侧再找同样的和。前缀和使任一段的和为常数时间。 $j$ 的枚举加上两侧线性扫描，总复杂度可接受。

先求出前缀和数组 s。

然后遍历 j 所有可能的位置，对于每个 j，找出 i，使得前两个子数组的和相等。同时将和添加到哈希表中。

接着对于每个 j，找出 k，使得后两个子数组的和相等，然后判断哈希表中是否存在该和，如果存在，则找到满足条件的三元组 (i, j, k)，返回 true。

否则遍历结束返回 false。

时间复杂度 $O(n^2)$。

func splitArray(nums []int) bool {
	n := len(nums)
	s := make([]int, n+1)
	for i, v := range nums {
		s[i+1] = s[i] + v
	}
	for j := 3; j < n-3; j++ {
		seen := map[int]bool{}
		for i := 1; i < j-1; i++ {
			if s[i] == s[j]-s[i+1] {
				seen[s[i]] = true
			}
		}
		for k := j + 2; k < n-1; k++ {
			if s[n]-s[k+1] == s[k]-s[j+1] && seen[s[n]-s[k+1]] {
				return true
			}
		}
	}
	return false
}

力扣原题 · Doocs 题解来源

560. 和为 K 的子数组

中等1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

 

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

 

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

方法一：哈希表 + 前缀和 · Go 实现

思考

统计和为 $k$ 的子数组个数。枚举两端是 $O(n^2)$，在 $n\le 2\times {10}^4$ 时偏紧。

若前缀和为 $s$，则需要此前有多少个前缀等于 $s-k$。哈希表统计已出现的前缀和次数，初值 $\mathit{\text{cnt}}[0]=1$ 表示空前缀。边走边查再更新，避免用到当前下标自己。

我们定义一个哈希表 $\mathit{\text{cnt}}$，用于存储数组 $\mathit{\text{nums}}$ 的前缀和出现的次数。初始时，我们将 $\mathit{\text{cnt}}[0]$ 的值设为 $1$，表示前缀和 $0$ 出现了一次。

我们遍历数组 $\mathit{\text{nums}}$，计算前缀和 $\mathit{\text{s}}$，然后将 $\mathit{\text{cnt}}[s-k]$ 的值累加到答案中，并将 $\mathit{\text{cnt}}[s]$ 的值增加 $1$。

遍历结束后，我们返回答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

func subarraySum(nums []int, k int) (ans int) {
	cnt := map[int]int{0: 1}
	s := 0
	for _, x := range nums {
		s += x
		ans += cnt[s-k]
		cnt[s]++
	}
	return
}

力扣原题 · Doocs 题解来源

724. 寻找数组的中心下标

简单1 种解法

标签：数组、前缀和

题目、示例与约束

给你一个整数数组 nums ，请计算数组的 中心下标 。

数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。

如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。

如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。

 

示例 1：

输入：nums = [1, 7, 3, 6, 5, 6]
输出：3
解释：
中心下标是 3 。
左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，
右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。

示例 2：

输入：nums = [1, 2, 3]
输出：-1
解释：
数组中不存在满足此条件的中心下标。

示例 3：

输入：nums = [2, 1, -1]
输出：0
解释：
中心下标是 0 。
左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），
右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。

 

提示：

• 1 <= nums.length <= 104
• -1000 <= nums[i] <= 1000

 

注意：本题与主站 1991 题相同：https://leetcode.cn/problems/find-the-middle-index-in-array/

方法一：前缀和 · Go 实现

思考

寻找左侧和等于右侧和的下标。 $n\le {10}^4$，对每个位置重算左右和为 $O(n^2)$，可以再压一档。

左右两侧之和的总和是固定的：若已知数组总和 $S$，则下标 $i$ 满足 $2\cdot \mathit{\text{left}}+nums[i]=S$。从左扫一遍维护左侧和即可。

实现上令 $\mathit{\text{right}}$ 初值为总和，遇到 $x$ 先从右侧减去，再与 $\mathit{\text{left}}$ 比较，最后把 $x$ 加入左侧。额外空间 $O(1)$。

我们定义变量 $left$ 表示数组 $\mathit{\text{nums}}$ 中下标 $i$ 左侧元素之和，变量 $right$ 表示数组 $\mathit{\text{nums}}$ 中下标 $i$ 右侧元素之和。初始时 $left=0$, $right=\sum _{i=0}^{n-1}nums[i]$。

遍历数组 $\mathit{\text{nums}}$，对于当前遍历到的数字 $x$，我们更新 $right=right-x$，此时如果 $left=right$，说明当前下标 $i$ 就是中间位置，直接返回即可。否则，我们更新 $left=left+x$，继续遍历下一个数字。

遍历结束，如果没有找到中间位置，返回 $-1$。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

相似题目：

• 1991. 找到数组的中间位置
• 2574. 左右元素和的差值

func pivotIndex(nums []int) int {
	var left, right int
	for _, x := range nums {
		right += x
	}
	for i, x := range nums {
		right -= x
		if left == right {
			return i
		}
		left += x
	}
	return -1
}

力扣原题 · Doocs 题解来源

798. 得分最高的最小轮调

困难1 种解法

标签：数组、前缀和

题目、示例与约束

给你一个数组 nums，我们可以将它按一个非负整数 k 进行轮调，这样可以使数组变为 [nums[k], nums[k + 1], ... nums[nums.length - 1], nums[0], nums[1], ..., nums[k-1]] 的形式。此后，任何值小于或等于其索引的项都可以记作一分。

• 例如，数组为 nums = [2,4,1,3,0]，我们按 k = 2 进行轮调后，它将变成 [1,3,0,2,4]。这将记为 3 分，因为 1 > 0 [不计分]、3 > 1 [不计分]、0 <= 2 [计 1 分]、2 <= 3 [计 1 分]，4 <= 4 [计 1 分]。

在所有可能的轮调中，返回我们所能得到的最高分数对应的轮调下标 k 。如果有多个答案，返回满足条件的最小的下标 k 。

 

示例 1：

输入：nums = [2,3,1,4,0]
输出：3
解释：
下面列出了每个 k 的得分：
k = 0,  nums = [2,3,1,4,0],    score 2
k = 1,  nums = [3,1,4,0,2],    score 3
k = 2,  nums = [1,4,0,2,3],    score 3
k = 3,  nums = [4,0,2,3,1],    score 4
k = 4,  nums = [0,2,3,1,4],    score 3
所以我们应当选择 k = 3，得分最高。

示例 2：

输入：nums = [1,3,0,2,4]
输出：0
解释：
nums 无论怎么变化总是有 3 分。
所以我们将选择最小的 k，即 0。

 

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] < nums.length

方法一：差分数组 · Go 实现

思考

轮转 $k$ 后， $nums[i]$ 移到 $(i-k)modn$，当新下标 $\ge nums[i]$ 时得一分。 $n\le {10}^5$，对每个 $k$ 计分过慢。

每个 $nums[i]$ 对一段连续的 $k$ 得分，这段是环上的区间。差分数组在左端 $+1$、右端 $-1$，前缀和即各 $k$ 的得分。

取得分最大且 $k$ 最小者。

对于每个数，都有一个固定的 k 生效区间。我们先利用差分，预处理每个数的 k 生效区间。有最多个数能覆盖到的 k 即是答案。

func bestRotation(nums []int) int {
	n := len(nums)
	d := make([]int, n)
	for i, v := range nums {
		l, r := (i+1)%n, (n+i+1-v)%n
		d[l]++
		d[r]--
	}
	mx, ans, s := -1, n, 0
	for k, t := range d {
		s += t
		if s > mx {
			mx = s
			ans = k
		}
	}
	return ans
}

力扣原题 · Doocs 题解来源

848. 字母移位

中等1 种解法

标签：数组、字符串、前缀和

题目、示例与约束

有一个由小写字母组成的字符串 s，和一个长度相同的整数数组 shifts。

我们将字母表中的下一个字母称为原字母的 移位 shift() （由于字母表是环绕的， 'z' 将会变成 'a'）。

• 例如，shift('a') = 'b', shift('t') = 'u', 以及 shift('z') = 'a'。

对于每个 shifts[i] = x ， 我们会将 s 中的前 i + 1 个字母移位 x 次。

返回 将所有这些移位都应用到 s 后最终得到的字符串 。

 

示例 1：

输入：s = "abc", shifts = [3,5,9]
输出："rpl"
解释： 
我们以 "abc" 开始。
将 S 中的第 1 个字母移位 3 次后，我们得到 "dbc"。
再将 S 中的前 2 个字母移位 5 次后，我们得到 "igc"。
最后将 S 中的这 3 个字母移位 9 次后，我们得到答案 "rpl"。

示例 2:

输入: s = "aaa", shifts = [1,2,3]
输出: "gfd"

 

提示:

• 1 <= s.length <= 105
• s 由小写英文字母组成
• shifts.length == s.length
• 0 <= shifts[i] <= 109

​​​​​​

方法一：后缀和 · Go 实现

思考

$\mathit{\text{shifts}}[i]$ 会使前 $i+1$ 个字母同时移位，直接按操作模拟在 $n\le {10}^5$ 且移位值很大时过慢。第 $i$ 个字母实际移位次数是后缀 $\mathit{\text{shifts}}[i:]$ 之和。

从右向左累加后缀和，对 $26$ 取模后改写该位。一次逆序扫描完成全部移位。

对于字符串 $s$ 中的每个字符，我们需要计算其最终的偏移量，即 $\mathit{\text{shifts}}[i]$ 与 $\mathit{\text{shifts}}[i+1]$ 与 $\mathit{\text{shifts}}[i+2]$ ... 的和。我们可以使用后缀和的思想，从后往前遍历 $\mathit{\text{shifts}}$，计算每个字符的最终偏移量，然后对 $26$ 取模，得到最终的字符。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。忽略答案的空间消耗，空间复杂度 $O(1)$。

func shiftingLetters(s string, shifts []int) string {
	t := 0
	n := len(s)
	cs := []byte(s)
	for i := n - 1; i >= 0; i-- {
		t += shifts[i]
		j := (int(cs[i]-'a') + t) % 26
		cs[i] = byte('a' + j)
	}
	return string(cs)
}

力扣原题 · Doocs 题解来源

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

中等1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。

子数组 是数组中 连续 的部分。

 

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：
有 7 个子数组满足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2:

输入: nums = [5], k = 9
输出: 0

 

提示:

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• 2 <= k <= 104

方法一：哈希表 + 前缀和 · Go 实现

思考

子数组和能被 $k$ 整除，当且仅当两端前缀和模 $k$ 相同。枚举区间为平方级。扫描时用计数表记录每个余数出现次数，当前余数 $s$ 的历史次数即为以该位置结尾的合法子数组数。初始 $cnt[0]=1$ 对应空前缀。

假设存在 $i\le j$，使得 $\mathit{\text{nums}}[i,..j]$ 的和能被 $k$ 整除，如果我们令 $s_i$ 表示 $\mathit{\text{nums}}[0,..i]$ 的和，令 $s_j$ 表示 $\mathit{\text{nums}}[0,..j]$ 的和，那么 $s_j-s_i$ 能被 $k$ 整除，即 $(s_j-s_i)modk=0$，也即 $s_{j}modk=s_{i}modk$。因此，我们可以用哈希表统计前缀和模 $k$ 的值的个数，从而快速判断是否存在满足条件的子数组。

我们用一个哈希表 $\mathit{\text{cnt}}$ 统计前缀和模 $k$ 的值的个数，即 $\mathit{\text{cnt}}[i]$ 表示前缀和模 $k$ 的值为 $i$ 的个数。初始时 $\mathit{\text{cnt}}[0]=1$。用变量 $s$ 表示前缀和，初始时 $s=0$。

接下来，从左到右遍历数组 $\mathit{\text{nums}}$，对于遍历到的每个元素 $x$，我们计算 $s=(s+x)modk$，然后更新答案 $\mathit{\text{ans}}=\mathit{\text{ans}}+\mathit{\text{cnt}}[s]$，其中 $\mathit{\text{cnt}}[s]$ 表示前缀和模 $k$ 的值为 $s$ 的个数。最后我们将 $\mathit{\text{cnt}}[s]$ 的值加 $1$，继续遍历下一个元素。

最终，我们返回答案 $\mathit{\text{ans}}$。

注意，由于 $s$ 的值可能为负数，因此我们可以将 $s$ 模 $k$ 的结果加上 $k$，再对 $k$ 取模，以确保 $s$ 的值为非负数。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

func subarraysDivByK(nums []int, k int) (ans int) {
	cnt := map[int]int{0: 1}
	s := 0
	for _, x := range nums {
		s = ((s+x)%k + k) % k
		ans += cnt[s]
		cnt[s]++
	}
	return
}

力扣原题 · Doocs 题解来源

1074. 元素和为目标值的子矩阵数量

困难1 种解法

标签：数组、哈希表、矩阵、前缀和

题目、示例与约束

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。

子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的集合。

如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中部分坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。

 

示例 1：

输入：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0
输出：4
解释：四个只含 0 的 1x1 子矩阵。

示例 2：

输入：matrix = [[1,-1],[-1,1]], target = 0
输出：5
解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。

示例 3：

输入：matrix = [[904]], target = 0
输出：0

 

提示：

• 1 <= matrix.length <= 100
• 1 <= matrix[0].length <= 100
• -1000 <= matrix[i][j] <= 1000
• -10^8 <= target <= 10^8

方法一：枚举上下边界 + 前缀和 + 哈希表 · Go 实现

思考

四重枚举子矩阵在 $100\times 100$ 上为 $O(n^4)$，偏紧。固定上下边界后，每列压缩成一个数，问题变成「一维数组中和为 $\mathit{\text{target}}$ 的子数组个数」。

一维可用前缀和哈希：每加入 $x$ 就查询 $s-\mathit{\text{target}}$ 出现次数。上下边界 $O(n^2)$ 对，每对扫描一列。

累加所有边界对上 $f(\mathit{\text{col}})$ 的返回值。

我们可以枚举矩阵的上下边界 $i$ 和 $j$，每次算出当前上下边界内每列的元素和，记为数组 $col$，然后问题就转换为如何在数组 $col$ 中寻找和为目标值 $target$ 的子数组个数。我们累加这些子数组的个数，就是题目要求的答案。

那么题目就变成了：给定一个数组 $nums$ 和目标值 $target$，计算有多少个子数组的和为 $target$，我们可以通过函数 $f(nums,target)$ 来求解。

函数 $f(nums,target)$ 的计算方法如下：

• 定义一个哈希表 $d$，用来记录出现过的前缀和以及其出现次数，初始时 $d[0]=1$；
• 初始化变量 $s=0,cnt=0$，其中 $s$ 表示前缀和，而 $cnt$ 表示和为 $target$ 的子数组个数；
• 从左到右遍历数组 $nums$，对于当前遍历到的元素 $x$，更新前缀和 $s=s+x$，如果 $d[s-target]$ 的值存在，那么更新 $cnt=cnt+d[s-target]$，即子数组个数增加 $d[s-target]$。然后更新哈希表中元素 $d[s]$ 的值，即 $d[s]=d[s]+1$；继续遍历下一个元素；
• 遍历结束之后，返回子数组个数 $cnt$。

时间复杂度 $O(m^2\times n)$，空间复杂度 $O(n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func numSubmatrixSumTarget(matrix [][]int, target int) (ans int) {
	m, n := len(matrix), len(matrix[0])
	for i := 0; i < m; i++ {
		col := make([]int, n)
		for j := i; j < m; j++ {
			for k := 0; k < n; k++ {
				col[k] += matrix[j][k]
			}
			ans += f(col, target)
		}
	}
	return
}

func f(nums []int, target int) (cnt int) {
	d := map[int]int{0: 1}
	s := 0
	for _, x := range nums {
		s += x
		if v, ok := d[s-target]; ok {
			cnt += v
		}
		d[s]++
	}
	return
}

力扣原题 · Doocs 题解来源

1109. 航班预订统计

中等2 种解法

标签：数组、前缀和

题目、示例与约束

这里有 n 个航班，它们分别从 1 到 n 进行编号。

有一份航班预订表 bookings ，表中第 i 条预订记录 bookings[i] = [firsti, lasti, seatsi] 意味着在从 firsti 到 lasti （包含 firsti 和 lasti ）的 每个航班 上预订了 seatsi 个座位。

请你返回一个长度为 n 的数组 answer，里面的元素是每个航班预定的座位总数。

 

示例 1：

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
输出：[10,55,45,25,25]
解释：
航班编号        1   2   3   4   5
预订记录 1 ：   10  10
预订记录 2 ：       20  20
预订记录 3 ：       25  25  25  25
总座位数：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

示例 2：

输入：bookings = [[1,2,10],[2,2,15]], n = 2
输出：[10,25]
解释：
航班编号        1   2
预订记录 1 ：   10  10
预订记录 2 ：       15
总座位数：      10  25
因此，answer = [10,25]

 

提示：

• 1 <= n <= 2 * 104
• 1 <= bookings.length <= 2 * 104
• bookings[i].length == 3
• 1 <= firsti <= lasti <= n
• 1 <= seatsi <= 104

方法一：差分数组 · Go 实现

思考

每次预订给闭区间 $[\mathit{\text{first}},\mathit{\text{last}}]$ 加上同一增量。若对区间内每个航班逐格修改，总时间与区间长度之和成正比，最坏达 $O(nm)$。

差分数组在左端点 $+\mathit{\text{seats}}$、在 $\mathit{\text{last}}+1$ 处 $-\mathit{\text{seats}}$，把一次区间更新降为两次单点操作；最后对差分数组求前缀和，即还原每个航班的座位数。

我们注意到，每一次预订都是在某个区间 [first, last] 内的所有航班上预订了 seats 个座位。因此，我们可以利用差分数组的思想，对于每一次预订，将 first 位置的数加上 seats，将 last + 1 位置的数减去 seats。最后，对差分数组求前缀和，即可得到每个航班预定的座位总数。

时间复杂度 $O(n)$，其中 $n$ 为航班数。忽略答案的空间消耗，空间复杂度 $O(1)$。

func corpFlightBookings(bookings [][]int, n int) []int {
	ans := make([]int, n)
	for _, e := range bookings {
		first, last, seats := e[0], e[1], e[2]
		ans[first-1] += seats
		if last < n {
			ans[last] -= seats
		}
	}
	for i := 1; i < n; i++ {
		ans[i] += ans[i-1]
	}
	return ans
}

方法二：树状数组 + 差分思想 · Go 实现

思考

方法一的差分数组依赖最后一次整体前缀和，适合离线出答案。树状数组把「单点加、前缀查」均做到 $O(\log n)$：对 $\mathit{\text{first}}$ 加、 $\mathit{\text{last}}+1$ 减后，查询位置 $i$ 的前缀和即航班 $i$ 的座位数。本题无需在线查询，渐近略慢，作为区间更新的另一种实现。

我们也可以利用树状数组，结合差分的思想，来实现上述操作。我们可以将每一次预订看作是在某个区间 [first, last] 内的所有航班上预订了 seats 个座位。因此，我们可以对每一次预订，对树状数组的 first 位置加上 seats，对树状数组的 last + 1 位置减去 seats。最后，对树状数组每个位置求前缀和，即可得到每个航班预定的座位总数。

时间复杂度 $O(n\times \log n)$，空间复杂度 $O(n)$。其中 $n$ 为航班数。

以下是树状数组的基本介绍：

树状数组，也称作“二叉索引树”（Binary Indexed Tree）或 Fenwick 树。 它可以高效地实现如下两个操作：

1. 单点更新 update(x, delta)： 把序列 x 位置的数加上一个值 delta；
2. 前缀和查询 query(x)：查询序列 [1,...x] 区间的区间和，即位置 x 的前缀和。

这两个操作的时间复杂度均为 $O(\log n)$。

type BinaryIndexedTree struct {
	n int
	c []int
}

func newBinaryIndexedTree(n int) *BinaryIndexedTree {
	c := make([]int, n+1)
	return &BinaryIndexedTree{n, c}
}

func (this *BinaryIndexedTree) update(x, delta int) {
	for x <= this.n {
		this.c[x] += delta
		x += x & -x
	}
}

func (this *BinaryIndexedTree) query(x int) int {
	s := 0
	for x > 0 {
		s += this.c[x]
		x -= x & -x
	}
	return s
}

func corpFlightBookings(bookings [][]int, n int) []int {
	tree := newBinaryIndexedTree(n)
	for _, e := range bookings {
		first, last, seats := e[0], e[1], e[2]
		tree.update(first, seats)
		tree.update(last+1, -seats)
	}
	ans := make([]int, n)
	for i := range ans {
		ans[i] = tree.query(i + 1)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1314. 矩阵区域和

中等1 种解法

标签：数组、矩阵、前缀和

题目、示例与约束

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和： 

• i - k <= r <= i + k,
• j - k <= c <= j + k 且
• (r, c) 在矩阵内。

 

示例 1：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1
输出：[[12,21,16],[27,45,33],[24,39,28]]

示例 2：

输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2
输出：[[45,45,45],[45,45,45],[45,45,45]]

 

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= mat[i][j] <= 100

方法一：二维前缀和 · Go 实现

思考

每个位置要正方形邻域和。若对每个 $(i,j)$ 现场累加， $k$ 较大时为 $O(mn{k}^2)$。同一子矩形会被多次求和，二维前缀和把任意矩形降为四点容斥。

先建 $s[i][j]$ 表示左上 $i\times j$ 的和，再对每个格子把窗口裁到矩阵边界，用 $s[x_2+1][y_2+1]-s[x_1][y_2+1]-s[x_2+1][y_1]+s[x_1][y_1]$ 取值。

本题属于二维前缀和模板题。

我们定义 $s[i][j]$ 表示矩阵 $mat$ 前 $i$ 行，前 $j$ 列的元素和。那么 $s[i][j]$ 的计算公式为：

$$s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+mat[i-1][j-1]$$

这样我们就可以通过 $s$ 数组快速计算出任意矩形区域的元素和。

对于一个左上角坐标为 $(x_1,y_1)$，右下角坐标为 $(x_2,y_2)$ 的矩形区域的元素和，我们可以通过 $s$ 数组计算出来：

$$s[x_2+1][y_2+1]-s[x_1][y_2+1]-s[x_2+1][y_1]+s[x_1][y_1]$$

时间复杂度 $O(m\times n)$，空间复杂度 $O(m\times n)$。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

func matrixBlockSum(mat [][]int, k int) [][]int {
	m, n := len(mat), len(mat[0])
	s := make([][]int, m+1)
	for i := range s {
		s[i] = make([]int, n+1)
	}
	for i, row := range mat {
		for j, x := range row {
			s[i+1][j+1] = s[i][j+1] + s[i+1][j] - s[i][j] + x
		}
	}

	ans := make([][]int, m)
	for i := range ans {
		ans[i] = make([]int, n)
	}

	for i := 0; i < m; i++ {
		for j := 0; j < n; j++ {
			x1 := max(i-k, 0)
			y1 := max(j-k, 0)
			x2 := min(m-1, i+k)
			y2 := min(n-1, j+k)
			ans[i][j] = s[x2+1][y2+1] - s[x1][y2+1] - s[x2+1][y1] + s[x1][y1]
		}
	}

	return ans
}

力扣原题 · Doocs 题解来源

1413. 逐步求和得到正数的最小值

简单1 种解法

标签：数组、前缀和

题目、示例与约束

给你一个整数数组 nums 。你可以选定任意的 正数 startValue 作为初始值。

你需要从左到右遍历 nums 数组，并将 startValue 依次累加上 nums 数组中的值。

请你在确保累加和始终大于等于 1 的前提下，选出一个最小的 正数 作为 startValue 。

 

示例 1：

输入：nums = [-3,2,-3,4,2]
输出：5
解释：如果你选择 startValue = 4，在第三次累加时，和小于 1 。
                累加求和
                startValue = 4 | startValue = 5 | nums
                  (4 -3 ) = 1  | (5 -3 ) = 2    |  -3
                  (1 +2 ) = 3  | (2 +2 ) = 4    |   2
                  (3 -3 ) = 0  | (4 -3 ) = 1    |  -3
                  (0 +4 ) = 4  | (1 +4 ) = 5    |   4
                  (4 +2 ) = 6  | (5 +2 ) = 7    |   2

示例 2：

输入：nums = [1,2]
输出：1
解释：最小的 startValue 需要是正数。

示例 3：

输入：nums = [1,-2,-3]
输出：5

 

提示：

• 1 <= nums.length <= 100
• -100 <= nums[i] <= 100

方法一 · Go 实现

思考

逐步和必须始终至少为 $1$。设起始值为 $x$，则所有前缀和加上 $x$ 都不小于 $1$，即 $x\ge 1-min\mathit{\text{prefix}}$。 $x$ 本身还至少为 $1$。

$n\le 100$，一遍扫描即可同时得到前缀和与其最小值 $t$，答案为 $max(1,1-t)$。

func minStartValue(nums []int) int {
	s, t := 0, 10000
	for _, num := range nums {
		s += num
		if s < t {
			t = s
		}
	}
	if t < 0 {
		return 1 - t
	}
	return 1
}

力扣原题 · Doocs 题解来源

1422. 分割字符串的最大得分

简单1 种解法

标签：字符串、前缀和

题目、示例与约束

给你一个由若干 0 和 1 组成的字符串 s ，请你计算并返回将该字符串分割成两个 非空 子字符串（即 左 子字符串和 右 子字符串）所能获得的最大得分。

「分割字符串的得分」为 左 子字符串中 0 的数量加上 右 子字符串中 1 的数量。

 

示例 1：

输入：s = "011101"
输出：5 
解释：
将字符串 s 划分为两个非空子字符串的可行方案有：
左子字符串 = "0" 且 右子字符串 = "11101"，得分 = 1 + 4 = 5 
左子字符串 = "01" 且 右子字符串 = "1101"，得分 = 1 + 3 = 4 
左子字符串 = "011" 且 右子字符串 = "101"，得分 = 1 + 2 = 3 
左子字符串 = "0111" 且 右子字符串 = "01"，得分 = 1 + 1 = 2 
左子字符串 = "01110" 且 右子字符串 = "1"，得分 = 2 + 1 = 3

示例 2：

输入：s = "00111"
输出：5
解释：当 左子字符串 = "00" 且 右子字符串 = "111" 时，我们得到最大得分 = 2 + 3 = 5

示例 3：

输入：s = "1111"
输出：3

 

提示：

• 2 <= s.length <= 500
• 字符串 s 仅由字符 '0' 和 '1' 组成。

方法一：计数 · Go 实现

思考

$n\le 500$，对每个切点分别数左右 $0$、 $1$ 可行，但会重复扫描。分数是左段 $0$ 的个数加右段 $1$ 的个数。

先统计全串的 $1$ 作为右段初值，再从左到右移动切点：遇 $0$ 则左计数加一，遇 $1$ 则右计数减一，维护 $l+r$ 的最大值。最后一位不能切开。

我们用两个变量 $l$ 和 $r$ 分别记录左子字符串中 $0$ 的数量和右子字符串中 $1$ 的数量。初始时 $l=0$，而 $r$ 则等于字符串 $s$ 中 $1$ 的数量。

遍历字符串 $s$ 的前 $n-1$ 个字符，对于每一个位置 $i$，如果 $s[i]=0$，则 $l$ 自增 $1$，否则 $r$ 自减 $1$。然后我们更新答案为 $l+r$ 的最大值。

时间复杂度 $O(n)$，其中 $n$ 为字符串 $s$ 的长度。空间复杂度 $O(1)$。

func maxScore(s string) (ans int) {
	l, r := 0, strings.Count(s, "1")
	for _, c := range s[:len(s)-1] {
		if c == '0' {
			l++
		} else {
			r--
		}
		ans = max(ans, l+r)
	}
	return
}

力扣原题 · Doocs 题解来源

1480. 一维数组的动态和

简单1 种解法

标签：数组、前缀和

题目、示例与约束

给你一个数组 nums 。数组「动态和」的计算公式为：runningSum[i] = sum(nums[0]…nums[i]) 。

请返回 nums 的动态和。

 

示例 1：

输入：nums = [1,2,3,4]
输出：[1,3,6,10]
解释：动态和计算过程为 [1, 1+2, 1+2+3, 1+2+3+4] 。

示例 2：

输入：nums = [1,1,1,1,1]
输出：[1,2,3,4,5]
解释：动态和计算过程为 [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1] 。

示例 3：

输入：nums = [3,1,2,10,1]
输出：[3,4,6,16,17]

 

提示：

• 1 <= nums.length <= 1000
• -10^6 <= nums[i] <= 10^6

方法一：前缀和 · Go 实现

思考

输出每个前缀的和。 $n\le 1000$，一次 accumulate 即可。

我们直接遍历数组，对于当前元素 $nums[i]$，我们将其与前缀和 $nums[i-1]$ 相加，即可得到当前元素的前缀和 $nums[i]$。

时间复杂度 $O(n)$，其中 $n$ 为数组长度。空间复杂度 $O(1)$。

func runningSum(nums []int) []int {
	for i := 1; i < len(nums); i++ {
		nums[i] += nums[i-1]
	}
	return nums
}

力扣原题 · Doocs 题解来源

1588. 所有奇数长度子数组的和

简单2 种解法

标签：数组、数学、前缀和

题目、示例与约束

给你一个正整数数组 arr ，请你计算所有可能的奇数长度子数组的和。

子数组 定义为原数组中的一个连续子序列。

请你返回 arr 中 所有奇数长度子数组的和 。

 

示例 1：

输入：arr = [1,4,2,5,3]
输出：58
解释：所有奇数长度子数组和它们的和为：
[1] = 1
[4] = 4
[2] = 2
[5] = 5
[3] = 3
[1,4,2] = 7
[4,2,5] = 11
[2,5,3] = 10
[1,4,2,5,3] = 15
我们将所有值求和得到 1 + 4 + 2 + 5 + 3 + 7 + 11 + 10 + 15 = 58

示例 2：

输入：arr = [1,2]
输出：3
解释：总共只有 2 个长度为奇数的子数组，[1] 和 [2]。它们的和为 3 。

示例 3：

输入：arr = [10,11,12]
输出：66

 

提示：

• 1 <= arr.length <= 100
• 1 <= arr[i] <= 1000

 

进阶：

你可以设计一个 O(n) 时间复杂度的算法解决此问题吗？

方法一：动态规划 · Go 实现

思考

求所有奇数长度子数组的元素和。 $n$ 通常不超过 $100$，三重循环可过，但会重复累加同一元素。以 $i$ 结尾的奇数长、偶数长子数组个数有闭式。

令 $f[i]$、 $g[i]$ 分别为以 $i$ 结尾的奇数长、偶数长子数组之和。奇数段由上一位置的偶数段接上 $arr[i]$ 得到，个数为 $i/2+1$；偶数段对称。答案累加全部 $f[i]$。

我们定义两个长度为 $n$ 的数组 $f$ 和 $g$，其中 $f[i]$ 表示以 $\mathit{\text{arr}}[i]$ 结尾的长度为奇数的子数组的和，而 $g[i]$ 表示以 $\mathit{\text{arr}}[i]$ 结尾的长度为偶数的子数组的和。初始时 $f[0]=\mathit{\text{arr}}[0]$，而 $g[0]=0$。答案即为 $\sum _{i=0}^{n-1}f[i]$。

当 $i>0$ 时，考虑 $f[i]$ 和 $g[i]$ 如何进行状态转移：

对于状态 $f[i]$，元素 $\mathit{\text{arr}}[i]$ 可以与前面的 $g[i-1]$ 组成一个长度为奇数的子数组，一共可以组成的子数组个数为 $(i/2)+1$ 个，因此 $f[i]=g[i-1]+\mathit{\text{arr}}[i]\times ((i/2)+1)$。

对于状态 $g[i]$，当 $i=0$ 时，没有长度为偶数的子数组，因此 $g[0]=0$；当 $i>0$ 时，元素 $\mathit{\text{arr}}[i]$ 可以与前面的 $f[i-1]$ 组成一个长度为偶数的子数组，一共可以组成的子数组个数为 $(i+1)/2$ 个，因此 $g[i]=f[i-1]+\mathit{\text{arr}}[i]\times ((i+1)/2)$。

最终答案即为 $\sum _{i=0}^{n-1}f[i]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{arr}}$ 的长度。

func sumOddLengthSubarrays(arr []int) (ans int) {
	n := len(arr)
	f := make([]int, n)
	g := make([]int, n)
	f[0] = arr[0]
	ans = f[0]
	for i := 1; i < n; i++ {
		f[i] = g[i-1] + arr[i]*(i/2+1)
		g[i] = f[i-1] + arr[i]*((i+1)/2)
		ans += f[i]
	}
	return
}

方法二：动态规划（空间优化） · Go 实现

思考

每个状态只读前一位的 $f,g$，两个滚动变量即可。时间仍线性，额外数组可以去掉。

我们注意到，状态 $f[i]$ 和 $g[i]$ 的值只与 $f[i-1]$ 和 $g[i-1]$ 有关，因此我们可以使用两个变量 $f$ 和 $g$ 分别记录 $f[i-1]$ 和 $g[i-1]$ 的值，从而优化空间复杂度。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。

func sumOddLengthSubarrays(arr []int) (ans int) {
	f, g := arr[0], 0
	ans = f
	for i := 1; i < len(arr); i++ {
		ff := g + arr[i]*(i/2+1)
		gg := f + arr[i]*((i+1)/2)
		f, g = ff, gg
		ans += f
	}
	return
}

力扣原题 · Doocs 题解来源

1590. 使数组和能被 P 整除

中等1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给你一个正整数数组 nums，请你移除 最短 子数组（可以为 空），使得剩余元素的 和 能被 p 整除。 不允许 将整个数组都移除。

请你返回你需要移除的最短子数组的长度，如果无法满足题目要求，返回 -1 。

子数组 定义为原数组中连续的一组元素。

 

示例 1：

输入：nums = [3,1,4,2], p = 6
输出：1
解释：nums 中元素和为 10，不能被 p 整除。我们可以移除子数组 [4] ，剩余元素的和为 6 。

示例 2：

输入：nums = [6,3,5,2], p = 9
输出：2
解释：我们无法移除任何一个元素使得和被 9 整除，最优方案是移除子数组 [5,2] ，剩余元素为 [6,3]，和为 9 。

示例 3：

输入：nums = [1,2,3], p = 3
输出：0
解释：和恰好为 6 ，已经能被 3 整除了。所以我们不需要移除任何元素。

示例  4：

输入：nums = [1,2,3], p = 7
输出：-1
解释：没有任何方案使得移除子数组后剩余元素的和被 7 整除。

示例 5：

输入：nums = [1000000000,1000000000,1000000000], p = 3
输出：0

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 109
• 1 <= p <= 109

方法一：前缀和 + 哈希表 · Go 实现

思考

删除最短子数组，使剩余元素之和能被 $p$ 整除。 $n\le {10}^5$，不能枚举子数组。设总和模 $p$ 为 $k$，删除段的和也必须模 $p$ 等于 $k$。

扫描前缀和模 $p$，用哈希表记下每种余数最近一次出现的位置。当前余数为 $cur$ 时，查找余数 $(cur-k)modp$ 的最近下标，两者之间即为候选删除段。全程删除则无解。

我们可以先求出数组 $\mathit{\text{nums}}$ 所有元素之和模 $p$ 的值，记为 $k$。如果 $k$ 为 $0$，说明数组 $\mathit{\text{nums}}$ 所有元素之和就是 $p$ 的倍数，直接返回 $0$ 即可。

如果 $k$ 不为 $0$，我们需要找到一个最短的子数组，使得删除该子数组后，剩余元素之和模 $p$ 的值为 $0$。

我们可以遍历数组 $\mathit{\text{nums}}$，维护当前的前缀和模 $p$ 的值，记为 $cur$。用哈希表 $last$ 记录每个前缀和模 $p$ 的值最后一次出现的位置。

如果当前存在一个以 $\mathit{\text{nums}}[i]$ 结尾的子数组，使得删除该子数组后，剩余元素之和模 $p$ 的值为 $0$。也就是说，我们需要找到此前的一个前缀和模 $p$ 的值为 $target$ 的位置 $j$，使得 $(target+k-cur)modp=0$。如果找到，我们就可以将 $j+1$ 到 $i$ 这一段闭区间子数组 $\mathit{\text{nums}}[j+1,..i]$ 删除，使得剩余元素之和模 $p$ 的值为 $0$。

因此，如果存在一个 $target=(cur-k+p)modp$，那么我们可以更新答案为 $min(ans,i-j)$。接下来，我们更新 $last[cur]$ 的值为 $i$。继续遍历数组 $\mathit{\text{nums}}$，直到遍历结束，即可得到答案。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

func minSubarray(nums []int, p int) int {
	k := 0
	for _, x := range nums {
		k = (k + x) % p
	}
	if k == 0 {
		return 0
	}
	last := map[int]int{0: -1}
	n := len(nums)
	ans := n
	cur := 0
	for i, x := range nums {
		cur = (cur + x) % p
		target := (cur - k + p) % p
		if j, ok := last[target]; ok {
			ans = min(ans, i-j)
		}
		last[cur] = i
	}
	if ans == n {
		return -1
	}
	return ans
}

力扣原题 · Doocs 题解来源

1664. 生成平衡数组的方案数

中等1 种解法

标签：数组、前缀和

题目、示例与约束

给你一个整数数组 nums 。你需要选择 恰好 一个下标（下标从 0 开始）并删除对应的元素。请注意剩下元素的下标可能会因为删除操作而发生改变。

比方说，如果 nums = [6,1,7,4,1] ，那么：

• 选择删除下标 1 ，剩下的数组为 nums = [6,7,4,1] 。
• 选择删除下标 2 ，剩下的数组为 nums = [6,1,4,1] 。
• 选择删除下标 4 ，剩下的数组为 nums = [6,1,7,4] 。

如果一个数组满足奇数下标元素的和与偶数下标元素的和相等，该数组就是一个 平衡数组 。

请你返回删除操作后，剩下的数组 nums 是 平衡数组 的 方案数 。

 

示例 1：

输入：nums = [2,1,6,4]
输出：1
解释：
删除下标 0 ：[1,6,4] -> 偶数元素下标为：1 + 4 = 5 。奇数元素下标为：6 。不平衡。
删除下标 1 ：[2,6,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：6 。平衡。
删除下标 2 ：[2,1,4] -> 偶数元素下标为：2 + 4 = 6 。奇数元素下标为：1 。不平衡。
删除下标 3 ：[2,1,6] -> 偶数元素下标为：2 + 6 = 8 。奇数元素下标为：1 。不平衡。
只有一种让剩余数组成为平衡数组的方案。

示例 2：

输入：nums = [1,1,1]
输出：3
解释：你可以删除任意元素，剩余数组都是平衡数组。

示例 3：

输入：nums = [1,2,3]
输出：0
解释：不管删除哪个元素，剩下数组都不是平衡数组。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 104

方法一：枚举 + 前缀和 · Go 实现

思考

删一个下标后奇偶位之和相等的方案数。 $n$ 达 ${10}^5$，删除后右侧奇偶对调，可用原数组的奇偶前缀/后缀在 $O(1)$ 内判定。

预处理偶数和 $s_1$、奇数和 $s_2$，扫描时用 $t_1,t_2$ 表示左侧已扫过的奇偶和，按当前下标奇偶代入删除后的两侧公式。

我们先预处理得到数组 nums 的偶数下标元素之和 $s_1$ 以及奇数下标元素之和 $s_2$。

然后从前往后枚举数组 nums 的每个元素 $v$，用变量 $t_1$ 和 $t_2$ 分别记录已遍历的偶数下标元素之和以及奇数下标元素之和。

我们观察发现，对于当前遍历到的元素 $v$，如果删除了，那么该元素之后的奇偶下标元素之和会发生交换。此时，我们先判断该位置下标 $i$ 是奇数还是偶数。

• 如果是偶数下标，删除该元素后，数组的奇数下标元素之和为 $t_2+s_1-t_1-v$，而偶数下标元素之和为 $t_1+s_2-t_2$，如果这两个和相等，那么就是一个平衡数组，答案加一。

• 如果是奇数下标，删除该元素后，数组的偶数下标元素之和为 $t_1+s_2-t_2-v$，而奇数下标元素之和为 $t_2+s_1-t_1$，如果这两个和相等，那么就是一个平衡数组，答案加一。

然后我们更新 $t_1$ 和 $t_2$，继续遍历下一个元素。遍历完数组后，即可得到答案。

时间复杂度 $O(n)$，其中 $n$ 为数组的长度。空间复杂度 $O(1)$。

func waysToMakeFair(nums []int) (ans int) {
	var s1, s2, t1, t2 int
	for i, v := range nums {
		if i%2 == 0 {
			s1 += v
		} else {
			s2 += v
		}
	}
	for i, v := range nums {
		if i%2 == 0 && t2+s1-t1-v == t1+s2-t2 {
			ans++
		}
		if i%2 == 1 && t2+s1-t1 == t1+s2-t2-v {
			ans++
		}
		if i%2 == 0 {
			t1 += v
		} else {
			t2 += v
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1674. 使数组互补的最少操作次数

中等1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给你一个长度为 偶数 n 的整数数组 nums 和一个整数 limit 。每一次操作，你可以将 nums 中的任何整数替换为 1 到 limit 之间的另一个整数。

如果对于所有下标 i（下标从 0 开始），nums[i] + nums[n - 1 - i] 都等于同一个数，则数组 nums 是 互补的 。例如，数组 [1,2,3,4] 是互补的，因为对于所有下标 i ，nums[i] + nums[n - 1 - i] = 5 。

返回使数组 互补 的 最少 操作次数。

 

示例 1：

输入：nums = [1,2,4,3], limit = 4
输出：1
解释：经过 1 次操作，你可以将数组 nums 变成 [1,2,2,3]（加粗元素是变更的数字）：
nums[0] + nums[3] = 1 + 3 = 4.
nums[1] + nums[2] = 2 + 2 = 4.
nums[2] + nums[1] = 2 + 2 = 4.
nums[3] + nums[0] = 3 + 1 = 4.
对于每个 i ，nums[i] + nums[n-1-i] = 4 ，所以 nums 是互补的。

示例 2：

输入：nums = [1,2,2,1], limit = 2
输出：2
解释：经过 2 次操作，你可以将数组 nums 变成 [2,2,2,2] 。你不能将任何数字变更为 3 ，因为 3 > limit 。

示例 3：

输入：nums = [1,2,1,2], limit = 2
输出：0
解释：nums 已经是互补的。

 

提示：

• n == nums.length
• 2 <= n <= 105
• 1 <= nums[i] <= limit <= 105
• n 是偶数。

方法一：差分数组 · Go 实现

思考

要把每对 $\mathit{\text{nums}}[i]+\mathit{\text{nums}}[n-1-i]$ 都变成同一个和 $s$，每次把一个数改到 $[1,\mathit{\text{limit}}]$。 $n$ 与 $\mathit{\text{limit}}$ 都可达 ${10}^5$，不能对每个 $s$ 再扫一遍数对。

一对 $(x,y)$（ $x\le y$）对 $s$ 的代价在若干区间上分别是 $2$、 $1$、 $0$、 $1$、 $2$，用差分数组把这些区间更新叠在 $[2,2\cdot \mathit{\text{limit}}]$ 上。

前缀和后取最小即最少修改次数。

假设最终的数组中，数对 $\mathit{\text{nums}}[i]$ 和 $\mathit{\text{nums}}[n-i-1]$ 的和为 $s$。

我们不妨设 $x$ 为 $\mathit{\text{nums}}[i]$ 和 $\mathit{\text{nums}}[n-i-1]$ 的较小值，设 $y$ 为 $\mathit{\text{nums}}[i]$ 和 $\mathit{\text{nums}}[n-i-1]$ 的较大值。

对于每一对数，我们有以下几种情况：

• 如果不需要替换，那么 $x+y=s$。
• 如果替换一次，那么 $x+1\le s\le y+\mathit{\text{limit}}$。
• 如果替换两次，那么 $2\le s\le x$ 或 $y+\mathit{\text{limit}}+1\le s\le 2\times \mathit{\text{limit}}$。

即：

• 在 $[2,..x]$ 范围内，需要替换 $2$ 次。
• 在 $[x+1,..x+y-1]$ 范围内，需要替换 $1$ 次。
• 在 $[x+y]$ 时，不需要替换。
• 在 $[x+y+1,..y+\mathit{\text{limit}}]$ 范围内，需要替换 $1$ 次。
• 在 $[y+\mathit{\text{limit}}+1,..2\times \mathit{\text{limit}}]$ 范围内，需要替换 $2$ 次。

我们枚举每一个数对，利用差分数组，更新每个数对在不同区间范围内的替换次数。

最后，我们求出下标 $2$ 到 $2\times \mathit{\text{limit}}$ 的前缀和中的最小值，即为最少的替换次数。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 $\mathit{\text{nums}}$ 的长度。

相似题目：

• 3224. 使差值相等的最少数组改动次数

func minMoves(nums []int, limit int) int {
	n := len(nums)
	d := make([]int, 2*limit+2)
	for i := 0; i < n/2; i++ {
		x, y := nums[i], nums[n-1-i]
		if x > y {
			x, y = y, x
		}
		d[2] += 2
		d[x+1] -= 2
		d[x+1] += 1
		d[x+y] -= 1
		d[x+y+1] += 1
		d[y+limit+1] -= 1
		d[y+limit+1] += 2
	}
	ans, s := n, 0
	for _, x := range d[2:] {
		s += x
		ans = min(ans, s)
	}
	return ans
}

力扣原题 · Doocs 题解来源

1685. 有序数组中差绝对值之和

中等1 种解法

标签：数组、数学、前缀和

题目、示例与约束

给你一个 非递减 有序整数数组 nums 。

请你建立并返回一个整数数组 result，它跟 nums 长度相同，且result[i] 等于 nums[i] 与数组中所有其他元素差的绝对值之和。

换句话说， result[i] 等于 sum(|nums[i]-nums[j]|) ，其中 0 <= j < nums.length 且 j != i （下标从 0 开始）。

 

示例 1：

输入：nums = [2,3,5]
输出：[4,3,5]
解释：假设数组下标从 0 开始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。

示例 2：

输入：nums = [1,4,6,8,10]
输出：[24,15,13,15,21]

 

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i] <= nums[i + 1] <= 104

方法一：求和 + 枚举 · Go 实现

思考

数组已排序， $|x-y|$ 在左侧是 $x-y$、右侧是 $y-x$。对每个 $i$，绝对值之和可用左侧和、右侧和在 $O(1)$ 内写出。

记总加和 $s$、已扫加和 $t$，则 $\mathit{\text{ans}}[i]=x\cdot i-t+(s-t)-x\cdot (n-i)$，再把 $x$ 累进 $t$。

我们先求出数组 $nums$ 所有元素的和，记为 $s$，用变量 $t$ 记录当前已经枚举过的元素之和。

接下来枚举 $nums[i]$，那么 $ans[i]=nums[i]\times i-t+s-t-nums[i]\times (n-i)$，然后我们更新 $t$，即 $t=t+nums[i]$。继续枚举下一个元素，直到枚举完所有元素。

时间复杂度 $O(n)$，其中 $n$ 为数组 $nums$ 的长度。空间复杂度 $O(1)$。

func getSumAbsoluteDifferences(nums []int) (ans []int) {
	var s, t int
	for _, x := range nums {
		s += x
	}
	for i, x := range nums {
		v := x*i - t + s - t - x*(len(nums)-i)
		ans = append(ans, v)
		t += x
	}
	return
}

力扣原题 · Doocs 题解来源

1732. 找到最高海拔

简单1 种解法

标签：数组、前缀和

题目、示例与约束

有一个自行车手打算进行一场公路骑行，这条路线总共由 n + 1 个不同海拔的点组成。自行车手从海拔为 0 的点 0 开始骑行。

给你一个长度为 n 的整数数组 gain ，其中 gain[i] 是点 i 和点 i + 1 的 净海拔高度差（0 <= i < n）。请你返回 最高点的海拔 。

 

示例 1：

输入：gain = [-5,1,5,0,-7]
输出：1
解释：海拔高度依次为 [0,-5,-4,1,1,-6] 。最高海拔为 1 。

示例 2：

输入：gain = [-4,-3,-2,-1,4,3,2]
输出：0
解释：海拔高度依次为 [0,-4,-7,-9,-10,-6,-3,-1] 。最高海拔为 0 。

 

提示：

• n == gain.length
• 1 <= n <= 100
• -100 <= gain[i] <= 100

方法一：前缀和（差分数组） · Go 实现

思考

$\mathit{\text{gain}}$ 是相邻海拔之差，起点海拔为 $0$。最高点即差分数组前缀和的最大值。

从 $0$ 起累加 $\mathit{\text{gain}}$，同步记录前缀最大值。

我们假设每个点的海拔为 $h_i$，由于 $gain[i]$ 表示第 $i$ 个点和第 $i+1$ 个点的海拔差，因此 $gain[i]=h_{i+1}-h_i$。那么：

$$\sum _{i=0}^{n-1}gain[i]=h_1-h_0+h_2-h_1+\cdots +h_n-h_{n-1}=h_n-h_0=h_n$$

即：

$$h_{i+1}=\sum _{j=0}^{i}gain[j]$$

可以发现，每个点的海拔都可以通过前缀和的方式计算出来。因此，我们只需要遍历一遍数组，求出前缀和的最大值，即为最高点的海拔。

实际上题目中的 $gain$ 数组是一个差分数组，对差分数组求前缀和即可得到原海拔数组。然后求出原海拔数组的最大值即可。

时间复杂度 $O(n)$，空间复杂度 $O(1)$。其中 $n$ 为数组 $gain$ 的长度。

func largestAltitude(gain []int) (ans int) {
	h := 0
	for _, v := range gain {
		h += v
		if ans < h {
			ans = h
		}
	}
	return
}

力扣原题 · Doocs 题解来源

1737. 满足三条件之一需改变的最少字符数

中等1 种解法

标签：哈希表、字符串、计数、前缀和

题目、示例与约束

给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 ：

• a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
• b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
• a 和 b 都 由 同一个 字母组成。

返回达成目标所需的 最少 操作数。

 

示例 1：

输入：a = "aba", b = "caa"
输出：2
解释：满足每个条件的最佳方案分别是：
1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。

示例 2：

输入：a = "dabadd", b = "cda"
输出：3
解释：满足条件 1 的最佳方案是将 b 变为 "eee" 。

 

提示：

• 1 <= a.length, b.length <= 105
• a 和 b 只由小写字母组成

方法一：计数 + 枚举 · Go 实现

思考

三种目标：整段 $a$ 严格小于整段 $b$、相反、或两串都变成同一字母。字母只有 $26$ 个，可枚举分界或目标字母。

先计数。第三种对每个字母 $c$ 统计两串中非 $c$ 的个数。前两种枚举分界 $c$，把一侧全部改到 $c$ 之前、另一侧改到 $c$ 及之后。

三种最小值即为答案。

我们先统计字符串 $a$ 和 $b$ 中每个字母出现的次数，记为 $cn{t}_1$ 和 $cn{t}_2$。

然后考虑条件 $3$，即 $a$ 和 $b$ 中的每个字母都相同。我们只需要枚举最终的字母 $c$，然后统计 $a$ 和 $b$ 中不是 $c$ 的字母的个数，即为需要改变的字符个数。

然后考虑条件 $1$ 和 $2$，即 $a$ 中的每个字母都小于 $b$ 中的每个字母，或者 $b$ 中的每个字母都小于 $a$ 中的每个字母。对于条件 $1$，我们令字符串 $a$ 所有字符都小于字符 $c$，字符串 $b$ 所有字符都不小于 $c$，枚举 $c$ 找出最小的答案即可。条件 $2$ 同理。

最终的答案即为上述三种情况的最小值。

时间复杂度 $O(m+n+C^2)$，其中 $m$ 和 $n$ 分别为字符串 $a$ 和 $b$ 的长度，而 $C$ 为字符集大小。本题中 $C=26$。

func minCharacters(a string, b string) int {
	cnt1 := [26]int{}
	cnt2 := [26]int{}
	for _, c := range a {
		cnt1[c-'a']++
	}
	for _, c := range b {
		cnt2[c-'a']++
	}
	m, n := len(a), len(b)
	ans := m + n
	for i := 0; i < 26; i++ {
		ans = min(ans, m+n-cnt1[i]-cnt2[i])
	}
	f := func(cnt1, cnt2 [26]int) {
		for i := 1; i < 26; i++ {
			t := 0
			for j := i; j < 26; j++ {
				t += cnt1[j]
			}
			for j := 0; j < i; j++ {
				t += cnt2[j]
			}
			ans = min(ans, t)
		}
	}
	f(cnt1, cnt2)
	f(cnt2, cnt1)
	return ans
}

力扣原题 · Doocs 题解来源

1744. 你能在你最喜欢的那天吃到你最喜欢的糖果吗？

中等1 种解法

标签：数组、前缀和

题目、示例与约束

给你一个下标从 0 开始的正整数数组 candiesCount ，其中 candiesCount[i] 表示你拥有的第 i 类糖果的数目。同时给你一个二维数组 queries ，其中 queries[i] = [favoriteTypei, favoriteDayi, dailyCapi] 。

你按照如下规则进行一场游戏：

• 你从第 0 天开始吃糖果。
• 你在吃完 所有 第 i - 1 类糖果之前，不能 吃任何一颗第 i 类糖果。
• 在吃完所有糖果之前，你必须每天 至少 吃 一颗 糖果。

请你构建一个布尔型数组 answer ，用以给出 queries 中每一项的对应答案。此数组满足：

• answer.length == queries.length 。answer[i] 是 queries[i] 的答案。
• answer[i] 为 true 的条件是：在每天吃 不超过 dailyCapi 颗糖果的前提下，你可以在第 favoriteDayi 天吃到第 favoriteTypei 类糖果；否则 answer[i] 为 false 。

注意，只要满足上面 3 条规则中的第二条规则，你就可以在同一天吃不同类型的糖果。

请你返回得到的数组 answer 。

 

示例 1：

输入：candiesCount = [7,4,5,3,8], queries = [[0,2,2],[4,2,4],[2,13,1000000000]]
输出：[true,false,true]
提示：
1- 在第 0 天吃 2 颗糖果(类型 0），第 1 天吃 2 颗糖果（类型 0），第 2 天你可以吃到类型 0 的糖果。
2- 每天你最多吃 4 颗糖果。即使第 0 天吃 4 颗糖果（类型 0），第 1 天吃 4 颗糖果（类型 0 和类型 1），你也没办法在第 2 天吃到类型 4 的糖果。换言之，你没法在每天吃 4 颗糖果的限制下在第 2 天吃到第 4 类糖果。
3- 如果你每天吃 1 颗糖果，你可以在第 13 天吃到类型 2 的糖果。

示例 2：

输入：candiesCount = [5,2,6,4,1], queries = [[3,1,2],[4,10,3],[3,10,100],[4,100,30],[1,3,1]]
输出：[false,true,true,false,false]

 

提示：

• 1 <= candiesCount.length <= 105
• 1 <= candiesCount[i] <= 105
• 1 <= queries.length <= 105
• queries[i].length == 3
• 0 <= favoriteTypei < candiesCount.length
• 0 <= favoriteDayi <= 109
• 1 <= dailyCapi <= 109

方法一：前缀和 · Go 实现

思考

糖果必须按种类顺序吃，每天至少 $1$ 颗、至多 $\mathit{\text{dailyCap}}$ 颗。询问多，不能对每个询问模拟逐日食用。

前缀和 $s[t]$ 是第 $t$ 类之前的糖果总数。要在第 $\mathit{\text{day}}$ 天吃到类型 $t$，最慢也得在那天之前吃掉不到 $s[t+1]$ 颗，最快也不能在到达 $t$ 之前就把 $s[t]$ 吃完。

即 $\mathit{\text{day}}<s[t+1]$ 且 $(\mathit{\text{day}}+1)\cdot mx>s[t]$。对每个询问 $O(1)$ 判断。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为数组 candiesCount 的长度。

func canEat(candiesCount []int, queries [][]int) (ans []bool) {
	n := len(candiesCount)
	s := make([]int, n+1)
	for i, v := range candiesCount {
		s[i+1] = s[i] + v
	}
	for _, q := range queries {
		t, day, mx := q[0], q[1], q[2]
		least, most := day, (day+1)*mx
		ans = append(ans, least < s[t+1] && most > s[t])
	}
	return
}

力扣原题 · Doocs 题解来源

1769. 移动所有球到每个盒子所需的最小操作数

中等2 种解法

标签：数组、字符串、前缀和

题目、示例与约束

有 n 个盒子。给你一个长度为 n 的二进制字符串 boxes ，其中 boxes[i] 的值为 '0' 表示第 i 个盒子是 空 的，而 boxes[i] 的值为 '1' 表示盒子里有 一个 小球。

在一步操作中，你可以将 一个 小球从某个盒子移动到一个与之相邻的盒子中。第 i 个盒子和第 j 个盒子相邻需满足 abs(i - j) == 1 。注意，操作执行后，某些盒子中可能会存在不止一个小球。

返回一个长度为 n 的数组 answer ，其中 answer[i] 是将所有小球移动到第 i 个盒子所需的 最小 操作数。

每个 answer[i] 都需要根据盒子的 初始状态 进行计算。

 

示例 1：

输入：boxes = "110"
输出：[1,1,3]
解释：每个盒子对应的最小操作数如下：
1) 第 1 个盒子：将一个小球从第 2 个盒子移动到第 1 个盒子，需要 1 步操作。
2) 第 2 个盒子：将一个小球从第 1 个盒子移动到第 2 个盒子，需要 1 步操作。
3) 第 3 个盒子：将一个小球从第 1 个盒子移动到第 3 个盒子，需要 2 步操作。将一个小球从第 2 个盒子移动到第 3 个盒子，需要 1 步操作。共计 3 步操作。

示例 2：

输入：boxes = "001011"
输出：[11,8,5,4,3,4]

 

提示：

• n == boxes.length
• 1 <= n <= 2000
• boxes[i] 为 '0' 或 '1'

方法一：前缀和 · Go 实现

思考

把所有球移到盒子 $i$ 的代价是各球下标与 $i$ 的距离之和。 $n\le 2000$，对每个 $i$ 扫全部球可行，但可线性完成。

左（右）侧代价可由相邻位置递推：多一个左侧球，整体代价增加该球数。预处理 $left[i]$ 与 $right[i]$ 后相加。

我们可以预处理出每个位置 $i$ 左边的小球移动到 $i$ 的操作数，记为 $left[i]$；每个位置 $i$ 右边的小球移动到 $i$ 的操作数，记为 $right[i]$。那么答案数组的第 $i$ 个元素就是 $left[i]+right[i]$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 为 boxes 的长度。

func minOperations(boxes string) []int {
	n := len(boxes)
	left := make([]int, n)
	right := make([]int, n)
	for i, cnt := 1, 0; i < n; i++ {
		if boxes[i-1] == '1' {
			cnt++
		}
		left[i] = left[i-1] + cnt
	}
	for i, cnt := n-2, 0; i >= 0; i-- {
		if boxes[i+1] == '1' {
			cnt++
		}
		right[i] = right[i+1] + cnt
	}
	ans := make([]int, n)
	for i := range ans {
		ans[i] = left[i] + right[i]
	}
	return ans
}

方法二：前缀和（空间优化） · Go 实现

思考

方法一的左右数组只依赖前一格，可去掉额外数组：从左到右、再从右到左把递推值累加进 $ans$，额外空间降为常数。

方法一中 $left[i]$ 和 $right[i]$ 只依赖前一个位置，因此可以去掉这两个数组，从左到右、再从右到左各扫一遍，把结果累加到答案数组 $ans$ 上。

时间复杂度 $O(n)$，忽略答案数组的空间消耗，空间复杂度 $O(1)$。其中 $n$ 为 boxes 的长度。

func minOperations(boxes string) []int {
	n := len(boxes)
	ans := make([]int, n)
	for i, cnt := 1, 0; i < n; i++ {
		if boxes[i-1] == '1' {
			cnt++
		}
		ans[i] = ans[i-1] + cnt
	}
	for i, cnt, s := n-2, 0, 0; i >= 0; i-- {
		if boxes[i+1] == '1' {
			cnt++
		}
		s += cnt
		ans[i] += s
	}
	return ans
}

力扣原题 · Doocs 题解来源

1854. 人口最多的年份

简单1 种解法

标签：数组、计数、前缀和

题目、示例与约束

给你一个二维整数数组 logs ，其中每个 logs[i] = [birthi, deathi] 表示第 i 个人的出生和死亡年份。

年份 x 的 人口 定义为这一年期间活着的人的数目。第 i 个人被计入年份 x 的人口需要满足：x 在闭区间 [birthi, deathi - 1] 内。注意，人不应当计入他们死亡当年的人口中。

返回 人口最多 且 最早 的年份。

 

示例 1：

输入：logs = [[1993,1999],[2000,2010]]
输出：1993
解释：人口最多为 1 ，而 1993 是人口为 1 的最早年份。

示例 2：

输入：logs = [[1950,1961],[1960,1971],[1970,1981]]
输出：1960
解释： 
人口最多为 2 ，分别出现在 1960 和 1970 。
其中最早年份是 1960 。

 

提示：

• 1 <= logs.length <= 100
• 1950 <= birthi < deathi <= 2050

方法一：差分数组 · Go 实现

思考

求存活人数最多且最早的年份，年份仅在 $[1950,2050]$。若按年枚举再扫全部人生卒， $O(C\cdot n)$ 虽可通过，但每次都重复计数。

值域很小，用差分数组在出生年 $+1$、死亡年 $-1$，再扫一遍前缀和即可得到每年人口。记录最大前缀及其下标，加回偏移即答案。

我们注意到，年份的范围是 $[1950,..2050]$，因此我们可以将这些年份映射到一个长度为 $101$ 的数组 $d$ 中，数组的下标表示年份减去 $1950$ 的值。

接下来遍历 $logs$，对于每个人，我们将 $d[birt{h}_i-1950]$ 加 $1$，将 $d[deat{h}_i-1950]$ 减 $1$。最后遍历数组 $d$，求出前缀和的最大值，即为人口最多的年份，再加上 $1950$ 即为答案。

时间复杂度 $O(n)$，空间复杂度 $O(C)$。其中 $n$ 为数组 $logs$ 的长度；而 $C$ 为年份的范围大小，即 $2050-1950+1=101$。

func maximumPopulation(logs [][]int) int {
	d := [101]int{}
	offset := 1950
	for _, log := range logs {
		a, b := log[0]-offset, log[1]-offset
		d[a]++
		d[b]--
	}
	var s, mx, j int
	for i, x := range d {
		s += x
		if mx < s {
			mx = s
			j = i
		}
	}
	return j + offset
}

力扣原题 · Doocs 题解来源

1893. 检查是否区域内所有整数都被覆盖

简单1 种解法

标签：数组、哈希表、前缀和

题目、示例与约束

给你一个二维整数数组 ranges 和两个整数 left 和 right 。每个 ranges[i] = [starti, endi] 表示一个从 starti 到 endi 的 闭区间 。

如果闭区间 [left, right] 内每个整数都被 ranges 中 至少一个 区间覆盖，那么请你返回 true ，否则返回 false 。

已知区间 ranges[i] = [starti, endi] ，如果整数 x 满足 starti <= x <= endi ，那么我们称整数x 被覆盖了。

 

示例 1：

输入：ranges = [[1,2],[3,4],[5,6]], left = 2, right = 5
输出：true
解释：2 到 5 的每个整数都被覆盖了：
- 2 被第一个区间覆盖。
- 3 和 4 被第二个区间覆盖。
- 5 被第三个区间覆盖。

示例 2：

输入：ranges = [[1,10],[10,20]], left = 21, right = 21
输出：false
解释：21 没有被任何一个区间覆盖。

 

提示：

• 1 <= ranges.length <= 50
• 1 <= starti <= endi <= 50
• 1 <= left <= right <= 50

方法一：差分数组 · Go 实现

思考

判断 $[left,right]$ 是否都被给定区间覆盖。值域不超过 $50$，不必用线段树。

差分数组在每个 $[l,r]$ 的左端 $+1$、右端后一位 $-1$，前缀和即该点被覆盖次数。若 $[left,right]$ 中出现前缀和为 $0$ 的点则未完全覆盖。

我们可以使用差分数组的思想，创建一个长度为 $52$ 的差分数组 $\mathit{\text{diff}}$。

接下来，我们遍历数组 $\mathit{\text{ranges}}$，对于每个区间 $[l,r]$，我们令 $\mathit{\text{diff}}[l]$ 自增 $1$，而 $\mathit{\text{diff}}[r+1]$ 自减 $1$。

接着，我们遍历差分数组 $\mathit{\text{diff}}$，维护一个前缀和 $s$，对于每个位置 $i$，我们令 $s$ 自增 $\mathit{\text{diff}}[i]$，如果 $s\le 0$ 且 $left\le i\le right$，则说明区间 $[left,right]$ 中有一个整数 $i$ 没有被覆盖，返回 $\mathit{\text{false}}$。

如果遍历完差分数组 $\mathit{\text{diff}}$ 后都没有返回 $\mathit{\text{false}}$，则说明区间 $[left,right]$ 中的每个整数都被 $\mathit{\text{ranges}}$ 中至少一个区间覆盖，返回 $\mathit{\text{true}}$。

时间复杂度 $O(n+M)$，空间复杂度 $O(M)$。其中 $n$ 是数组 $\mathit{\text{ranges}}$ 的长度，而 $M$ 是区间的最大值，本题中 $M\le 50$。

func isCovered(ranges [][]int, left int, right int) bool {
	diff := [52]int{}
	for _, e := range ranges {
		l, r := e[0], e[1]
		diff[l]++
		diff[r+1]--
	}
	s := 0
	for i, x := range diff {
		s += x
		if s <= 0 && left <= i && i <= right {
			return false
		}
	}
	return true
}

力扣原题 · Doocs 题解来源

1895. 最大的幻方

中等1 种解法

标签：数组、矩阵、前缀和

题目、示例与约束

一个 k x k 的 幻方 指的是一个 k x k 填满整数的方格阵，且每一行、每一列以及两条对角线的和 全部相等 。幻方中的整数 不需要互不相同 。显然，每个 1 x 1 的方格都是一个幻方。

给你一个 m x n 的整数矩阵 grid ，请你返回矩阵中 最大幻方 的 尺寸 （即边长 k）。

 

示例 1：

输入：grid = [[7,1,4,5,6],[2,5,1,6,4],[1,5,4,3,2],[1,2,7,3,4]]
输出：3
解释：最大幻方尺寸为 3 。
每一行，每一列以及两条对角线的和都等于 12 。
- 每一行的和：5+1+6 = 5+4+3 = 2+7+3 = 12
- 每一列的和：5+5+2 = 1+4+7 = 6+3+3 = 12
- 对角线的和：5+4+3 = 6+4+2 = 12

示例 2：

输入：grid = [[5,1,3,1],[9,3,3,1],[1,3,3,8]]
输出：2

 

提示：

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 50
• 1 <= grid[i][j] <= 106

方法一：前缀和 + 枚举 · Go 实现

思考

幻方要求每行、每列、两条对角线和相等。矩阵不超过 $50\times 50$，可从大到小枚举边长，但每次暴力求和偏慢。

预处理行、列前缀和，检验一个子方阵时行和列和 $O(k)$ 取出，对角线再各走一遍。从 $k=min(m,n)$ 向下找，找到即返回。

我们定义 $\text{rowsum}[i][j]$ 表示矩阵第 $i$ 行前 $j$ 列的元素和，定义 $\text{colsum}[i][j]$ 表示矩阵第 $j$ 列前 $i$ 行的元素和。则对于任意子矩阵 $(x_1,y_1)$ 到 $(x_2,y_2)$，其第 $i$ 行的和可以表示为 $\text{rowsum}[i+1][y_2+1]-\text{rowsum}[i+1][y_1]$，其第 $j$ 列的和可以表示为 $\text{colsum}[x_2+1][j+1]-\text{colsum}[x_1][j+1]$。

我们枚举所有可能的子矩阵，并检查其是否为幻方。对于每个子矩阵，我们计算其每一行、每一列以及两条对角线的和，判断它们是否相等即可。

时间复杂度 $O(m\times n\times min(m,n{)}^2)$，空间复杂度 $O(m\times n)$。

func largestMagicSquare(grid [][]int) int {
	m, n := len(grid), len(grid[0])
	rowsum := make([][]int, m+1)
	colsum := make([][]int, m+1)
	for i := 0; i <= m; i++ {
		rowsum[i] = make([]int, n+1)
		colsum[i] = make([]int, n+1)
	}
	for i := 1; i < m+1; i++ {
		for j := 1; j < n+1; j++ {
			rowsum[i][j] = rowsum[i][j-1] + grid[i-1][j-1]
			colsum[i][j] = colsum[i-1][j] + grid[i-1][j-1]
		}
	}
	for k := min(m, n); k > 1; k-- {
		for i := 0; i+k-1 < m; i++ {
			for j := 0; j+k-1 < n; j++ {
				i2, j2 := i+k-1, j+k-1
				if check(grid, rowsum, colsum, i, j, i2, j2) {
					return k
				}
			}
		}
	}
	return 1
}

func check(grid, rowsum, colsum [][]int, x1, y1, x2, y2 int) bool {
	val := rowsum[x1+1][y2+1] - rowsum[x1+1][y1]
	for i := x1 + 1; i < x2+1; i++ {
		if rowsum[i+1][y2+1]-rowsum[i+1][y1] != val {
			return false
		}
	}
	for j := y1; j < y2+1; j++ {
		if colsum[x2+1][j+1]-colsum[x1][j+1] != val {
			return false
		}
	}
	s := 0
	for i, j := x1, y1; i <= x2; i, j = i+1, j+1 {
		s += grid[i][j]
	}
	if s != val {
		return false
	}
	s = 0
	for i, j := x1, y2; i <= x2; i, j = i+1, j-1 {
		s += grid[i][j]
	}
	if s != val {
		return false
	}
	return true
}

力扣原题 · Doocs 题解来源

1906. 查询差绝对值的最小值

中等1 种解法

标签：数组、前缀和

题目、示例与约束

一个数组 a 的 差绝对值的最小值 定义为：0 <= i < j < a.length 且 a[i] != a[j] 的 |a[i] - a[j]| 的 最小值。如果 a 中所有元素都 相同 ，那么差绝对值的最小值为 -1 。

• 比方说，数组 [5,2,3,7,2] 差绝对值的最小值是 |2 - 3| = 1 。注意答案不为 0 ，因为 a[i] 和 a[j] 必须不相等。

给你一个整数数组 nums 和查询数组 queries ，其中 queries[i] = [li, ri] 。对于每个查询 i ，计算 子数组 nums[li...ri] 中 差绝对值的最小值 ，子数组 nums[li...ri] 包含 nums 数组（下标从 0 开始）中下标在 li 和 ri 之间的所有元素（包含 li 和 ri 在内）。

请你返回 ans 数组，其中 ans[i] 是第 i 个查询的答案。

子数组 是一个数组中连续的一段元素。

|x| 的值定义为：

• 如果 x >= 0 ，那么值为 x 。
• 如果 x < 0 ，那么值为 -x 。

 

示例 1：

输入：nums = [1,3,4,8], queries = [[0,1],[1,2],[2,3],[0,3]]
输出：[2,1,4,1]
解释：查询结果如下：
- queries[0] = [0,1]：子数组是 [1,3] ，差绝对值的最小值为 |1-3| = 2 。
- queries[1] = [1,2]：子数组是 [3,4] ，差绝对值的最小值为 |3-4| = 1 。
- queries[2] = [2,3]：子数组是 [4,8] ，差绝对值的最小值为 |4-8| = 4 。
- queries[3] = [0,3]：子数组是 [1,3,4,8] ，差的绝对值的最小值为 |3-4| = 1 。

示例 2：

输入：nums = [4,5,2,2,7,10], queries = [[2,3],[0,2],[0,5],[3,5]]
输出：[-1,1,1,3]
解释：查询结果如下：
- queries[0] = [2,3]：子数组是 [2,2] ，差绝对值的最小值为 -1 ，因为所有元素相等。
- queries[1] = [0,2]：子数组是 [4,5,2] ，差绝对值的最小值为 |4-5| = 1 。
- queries[2] = [0,5]：子数组是 [4,5,2,2,7,10] ，差绝对值的最小值为 |4-5| = 1 。
- queries[3] = [3,5]：子数组是 [2,7,10] ，差绝对值的最小值为 |7-10| = 3 。

 

提示：

• 2 <= nums.length <= 105
• 1 <= nums[i] <= 100
• 1 <= queries.length <= 2 * 104
• 0 <= li < ri < nums.length

方法一 · Go 实现

思考

单次查询若排序再扫相邻差，代价为 $O((r-l)\log (r-l))$。 $n\le {10}^5$、 $q\le 2\times {10}^4$ 时，最坏会达到约 $O(qn\log n)$，不可接受。

值域仅为 $[1,100]$，区间内不同值的个数至多 $100$，最小绝对差必是区间内两个相邻不同取值之差。只需快速判断每个取值是否在 $[l,r]$ 中出现。

为此对每个取值维护前缀出现次数。查询时用前缀差得到区间内出现过的取值，按 $1$ 到 $100$ 顺序扫一遍相邻出现值即可。单次查询 $O(100)$。

func minDifference(nums []int, queries [][]int) []int {
	m, n := len(nums), len(queries)
	preSum := make([][101]int, m+1)
	for i := 1; i <= m; i++ {
		for j := 1; j <= 100; j++ {
			t := 0
			if nums[i-1] == j {
				t = 1
			}
			preSum[i][j] = preSum[i-1][j] + t
		}
	}

	ans := make([]int, n)
	for i := 0; i < n; i++ {
		left, right := queries[i][0], queries[i][1]+1
		t, last := 101, -1
		for j := 1; j <= 100; j++ {
			if preSum[right][j]-preSum[left][j] > 0 {
				if last != -1 {
					if t > j-last {
						t = j - last
					}
				}
				last = j
			}
		}
		if t == 101 {
			t = -1
		}
		ans[i] = t
	}
	return ans
}

力扣原题 · Doocs 题解来源