AI summary
type
status
date
slug
summary
category
tags
icon
password

前缀和

1314. 矩阵区域和

给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
  • i - k <= r <= i + k,
  • j - k <= c <= j + k 且
  • (r, c) 在矩阵内。
这道题可以直接套用前文 小而美的算法技巧：前缀和数组 中讲 304. 二维区域和检索 时实现的 NumMatrix 类，没什么难度。主要注意下通过 min, max 函数优雅避免索引越界的技巧，这个还是蛮常用的。
注意：preSum 数组下标是从 1 开始的，所以 [(0,0),(x,y)] 区间的和表示为 preSum[x+1][y+1] 。

724. 寻找数组的中心下标

给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
有了前缀和数组 preSum，就可以根据 preSum 快速计算 nums 中任意位置的左侧元素和右侧元素之和了。

前缀积

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

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
前缀和数组中两个元素之差是子数组元素之和，那么如果构造「前缀积」数组，两个元素相除就是子数组元素之和。但是题目要求不使用除法。
所以我们构造一个 prefix 数组记录「前缀积」，再用一个 suffix 记录「后缀积」，根据前缀和后缀积就能计算除了当前元素之外其他元素的积。
注意：prefix 的范围是 [1,n-1]，suffix 的范围是 [0,n-2]；[x,-1] 范围内的后缀积表示为 suffix[x-1]。
  • range(start, stop, step)
    • start：起始值（包含）。
    • stop：结束值（不包含）。
    • step：步长（每次递增或递减的值）。

1352. 最后 K 个数的乘积

请你实现一个「数字乘积类」ProductOfNumbers，要求支持下述两种方法：
1.add(int num)
  • 将数字 num 添加到当前数字列表的最后面。
2.getProduct(int k)
  • 返回当前数字列表中，最后 k 个数字的乘积。
  • 你可以假设当前列表中始终 至少 包含 k 个数字。
题目数据保证：任何时候，任一连续数字序列的乘积都在 32-bit 整数范围内，不会溢出。
前缀和和前缀积很类似，只不过乘积中如果有 0 需要特殊处理。当添加元素为 0 时重置 product；当 k 大于 product 长度时直接返回 0.

前缀和+哈希表

前缀和数组帮你快速计算子数组的元素之和，但如果让你寻找某个符合条件的子数组，怎么办？
比方说，让你在 nums 中寻找和为 target 的子数组，就算有前缀和数组的帮助，你也要写个嵌套 for 循环。
但我们可以借助哈希表记录每个前缀和对应的索引，这样就能快速计算目标和为 target 的子数组了：
这样，时间复杂度就从平方级降到了线性。以下是几道例题。

525. 连续数组

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
首先，我们做一个等价，题目让你找 0 和 1 数量相同的最长子数组，如果我们把 0 视作 -1，就把题目转变成了：寻找和为 0 的最长子数组。
涉及到和为 xxx 的子数组，就是要考察 前缀和技巧 和哈希表的结合使用了。
求和为 0 的最长子数组，相当于让你去 preSum 数组中找 i, j，使得 preSum[i] - preSum[j] == 0，其中 i > j 且 i - j 要尽可能大。
那么我们用一个哈希表 valToIndex 存储前缀和到索引的映射，给定任意 preSum[i]，我们都能通过 valToIndex 快速判断是否存在 j，使得 preSum[i] - preSum[j] == 0。
值得一提的是，我给的解法中 preSum 数组可以进一步简化成变量，这个优化可以留给你来做。
将 preSum 简化成变量，其实就是动态规划中的空间压缩，压缩后代码如下：

523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：
一个 好的子数组 是：
  • 长度 至少为 2 ，且
  • 子数组元素总和为 k 的倍数。
注意：
  • 子数组 是数组中 连续 的部分。
  • 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。
本题让你寻找长度至少为 2 且和为 k 的倍数的子数组，翻译一下就是：
寻找 i, j 使得 (preSum[i] - preSum[j]) % k == 0 且 i - j >= 2。
另外，(preSum[i] - preSum[j]) % k == 0 其实就是 preSum[i] % k == preSum[j] % k。(取余的性质)
所以我们使用一个哈希表，记录 preSum[j] % k 的值以及对应的索引，就可以迅速判断 preSum[i] 是否符合条件了。

560. 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
本题和前两题的最大区别在于，需要在维护 preSum 前缀和数组的同时动态维护 count 映射，而不能等到 preSum 计算完成后再处理 count，因为 count[need] 应该维护 preSum[0..i] 中值为 need 的元素个数。

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

给定一个数组 nums 和一个目标值 k，找到和等于 k 的最长连续子数组长度。如果不存在任意一个符合要求的子数组，则返回 0。
本题让你寻找长度最长的和为 k 的子数组，翻译一下就是：
寻找 i, j 使得 preSum[i] - preSum[j] == k 且 i - j 尽可能的大。
另外，preSum[i] - preSum[j] == k 其实就是 preSum[j] == preSum[i] - k。
所以我们使用一个哈希表，记录 preSum[i] 的值以及这个前缀和第一次出现的索引，就可以迅速判断 preSum[i] 是否符合条件并计算最长子数组长度了。代码和前面的 525. 连续数组 没啥区别，略了。

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

给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。
523. 连续的子数组和 和 560. 和为 K 的子数组 的结合，代码如下：

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

给你一份工作时间表 hours，上面记录着某一位员工每天的工作小时数。
我们认为当员工一天中的工作小时数大于 8 小时的时候，那么这一天就是「劳累的一天」。
所谓「表现良好的时间段」，意味在这段时间内，「劳累的天数」是严格 大于「不劳累的天数」。
请你返回「表现良好时间段」的最大长度。
题目说 hours[i] 以 8 作为分界线，那么我们就要条件反射地想到对数据进行「归一化」处理，比如把所有大于 8 的元素视为 +1，把所有小于 8 的元素视为 -1，这样一来，这道题就改造成了：计算数组中元素和大于 0 的子数组的最大长度。这样就转为了类似 525. 连续数组，但是这里是要求大于 0。
为什么第 2 种情况要找 s[i]−1，而不是 s[i]−2 或更小的一项？
是因为前缀和 s 是从 0 开始，要得到小于 0 的前缀和，s 的值必然是先下去再上来。比如 s-1, s-2, ..., s-x, s-x+1, ..., s, 所以对于任何可能的 s[i]-2，在其之前一定有 s[i]-1 存在。