【优选算法篇】前缀之美，后缀之韵：于数列深处追寻算法的动与静

C++ 前缀和详解：进阶题解与思维分析

前言

在前一篇文章中，我们讨论了前缀和的基本概念及其基础应用，展示了如何利用前缀和快速解决数组区间求和问题。在这篇文章中，我们将继续深入探讨前缀和的更多应用，尤其是在解决一些中级难度问题中的实用性和效率提升。

第二章：前缀和进阶应用

2.1 和为 k 的子数组（medium）

题目链接：560. 和为 K 的子数组

题目描述：

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

示例 1：

• 输入：nums = [1,1,1], k = 2
• 输出：2
• 解释：共有两个子数组的和为 2，分别是 [1,1] 和 [1,1]。

示例 2：

• 输入：nums = [1,2,3], k = 3
• 输出：2
• 解释：共有两个子数组的和为 3，分别是 [1,2] 和 [3]。

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

解法一（前缀和 + 哈希表）

算法思路：

我们可以通过划分所有以 i 为结尾的子数组，逐步计算这些子数组的和是否为 k。如果满足条件，则累加结果。

1. 外层循环（枚举所有以 i 结尾的子数组）：
   • 针对每一个位置 i，我们寻找与其满足和为 k 的连续子数组。
2. 查找条件：
   • 要使 t-i 的子数组和为 k，相当于找到位置 0-t-1 的和为 sum - k。
   • 通过累加 0-i 的前缀和 sum[i]，我们可以将此问题简化为查找 sum[i] - k 是否在 0-t-1 区间内存在。
3. 初始化 hash[0] = 1：
   • 这里的 hash[0] = 1 是为了在 t=0 时处理特殊情况。
   • 假设 t=0，即从数组的开始到 i 位置的子数组和为 k，这等价于查找从 0-t-1 的前缀和为 0。但 t=0 时，区间 0-t-1 为无效区间，因此初始化 hash[0] = 1 可以保证从起点开始的累加和为 k。

示例分析

假设 nums = [1, 2, 3]，k = 3：

1. 初始状态：hash[0] = 1
2. 遍历 nums 数组：
   • 第一次循环：sum = 1，在 hash 中记录 hash[1] = 1
   • 第二次循环：sum = 3，此时 sum - k = 0 存在于 hash，累积结果 ret = 1
   • 第三次循环：sum = 6，此时 sum - k = 3 存在于 hash，累积结果 ret = 2

最终结果为 2，即子数组 [1, 2] 和 [3] 满足和为 k。

C++代码实现

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 记录前缀和出现的次数
        hash[0] = 1; // 确保能统计到从起点到i的子数组和为k的情况
        int sum = 0, ret = 0;

        for(auto x : nums) {
            sum += x; // 计算当前前缀和
            if(hash.count(sum - k)) ret += hash[sum - k]; // 统计符合条件的前缀和个数
            hash[sum]++; // 更新前缀和出现次数
        }

        return ret;
    }
};

易错点提示

1. 哈希表初始化：
   • hash[0] = 1 是关键，确保统计从数组起点到 i 的子数组和为 k 的情况。
2. 前缀和更新顺序：
   • 遍历过程中，计算 sum 后先查找 hash[sum - k]，再更新 hash[sum]。
3. 返回值累加逻辑：
   • 查询 hash[sum - k] 的值并累加至 ret，每次查找到的值直接反映了符合条件的子数组数量。

代码解读

通过使用哈希表存储前缀和出现的次数，我们可以在一次遍历中快速找到和为 k 的子数组个数。

• 时间复杂度：O(n)，因为只需遍历数组一次。
• 空间复杂度：O(n)，最坏情况下，每个前缀和都唯一，存入哈希表。

2.2 和可被 K 整除的子数组（medium）

题目链接：974. 和可被 K 整除的子数组

题目描述：

给定一个整数数组 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 * 10^4
• -10^4 <= nums[i] <= 10^4
• 2 <= k <= 10^4

解法（前缀和 + 哈希表 + 同余定理）

算法思路：

目标是统计出和为 k 的倍数的子数组数量。通过利用前缀和和同余定理可以实现线性复杂度的解法：

1. 同余定理： 两个数如果相减的差能够被 k 整除，则它们的余数相同，即 (a - b) % k == 0 等价于 a % k == b % k。 因此，只要在遍历过程中，当前位置前缀和与之前某个前缀和的余数相同，即可认为它们之间的子数组和能被 k 整除。
2. 前缀和与余数的关系：
   • 用 sum[i] 表示从数组起始位置到 i 的累加和。对于位置 i，要找到多少个以 i 结尾且和可被 k 整除的子数组，就需要查找在 0 到 i-1 区间内，前缀和对 k 取余与 sum[i] % k 相同的前缀和出现次数。

1. 哈希表记录余数出现次数：
   • 通过哈希表 hash 存储每种余数的出现次数，遍历时如果 sum % k 在 hash 中出现过，表示到当前位置 i 存在相同余数的前缀和，可以形成满足条件的子数组。
   • 每次找到余数相同的前缀和时，将其次数累加到结果中，然后更新 hash。
2. 处理负数余数：
   • 在某些编程语言中（如 C++），负数取模保留负号。为了避免负数影响判断，我们将余数调整为非负，表达式为 (sum % k + k) % k。

详细示例

假设 nums = [4, 5, 0, -2, -3, 1]，k = 5：

1. 初始状态：hash[0] = 1，表示从数组开始的和能被 k 整除的情况。
2. 遍历数组，逐步计算前缀和 sum 及其余数 r = (sum % k + k) % k，然后在 hash 中查找相同余数出现次数并累加至结果中。
   • 第一次循环：sum = 4，r = 4
     • hash[4] = 1 更新
   • 第二次循环：sum = 9，r = 4
     • hash[4] 已存在，累加结果 ret += 1
     • 更新 hash[4] = 2
   • 第三次循环：sum = 9，r = 4
     • hash[4] 已存在，累加结果 ret += 2
     • 更新 hash[4] = 3
   • 第四次循环：sum = 7，r = 2
     • hash[2] = 1 更新
   • 第五次循环：sum = 4，r = 4
     • hash[4] 已存在，累加结果 ret += 3
     • 更新 hash[4] = 4
   • 第六次循环：sum = 5，r = 0
     • hash[0] 已存在，累加结果 ret += 1
     • 更新 hash[0] = 2

最终结果 ret = 7，即共有 7 个子数组满足和能被 k 整除的条件。

C++代码实现

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> hash; // 记录前缀和余数出现的次数
        hash[0] = 1; // 确保能统计到从起点到i的子数组和为k的情况

        int sum = 0, ret = 0;
        for(auto x : nums) {
            sum += x; // 计算当前位置的前缀和
            int r = (sum % k + k) % k; // 修正后的余数

            if(hash.count(r)) ret += hash[r]; // 统计符合条件的余数出现次数
            hash[r]++; // 更新当前余数出现次数
        }

        return ret;
    }
};

易错点提示

1. 初始化 hash[0] = 1：
   • 为了处理从数组起点到 i 的子数组和能被 k 整除的情况，例如当 sum[i] % k == 0 时，需要提前初始化 hash[0] = 1，否则初始状态无法统计正确的结果。
2. 负数取模的修正：
   • 负数取模在 C++ 中保留负号。例如，-1 % 5 = -1。为了保证余数为非负，我们使用 (sum % k + k) % k 表达式，确保余数始终落在 [0, k-1] 范围。
3. 返回值累加逻辑：
   • 每次 sum % k 在哈希表中找到时，将其对应的次数累加到 ret 中，即前缀和为 i 的位置符合条件的子数组个数。

代码解读

我们使用前缀和和同余定理，将问题简化为寻找具有相同余数的前缀和数量。在一次遍历中快速统计出满足条件的子数组数量。

• 时间复杂度：O(n)，因为只需遍历数组一次。
• 空间复杂度：O(k)，哈希表存储 k 种余数

2.3 连续数组（medium）

题目链接：525. 连续数组

题目描述：

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

示例 1：

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

示例 2：

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

提示：

• 1 <= nums.length <= 10^5
• nums[i] 不是 0 就是 1

解法（前缀和 + 哈希表）

算法思路：

• 将 0 视为 -1，1 视为 1，这样问题转化为寻找连续区间的和为 0。
• 使用前缀和来记录当前位置的和，目标是找到第一个与当前和相等的前缀和的位置，以便计算出最长子数组的长度。

1. 初始化：
   • 使用哈希表记录每种前缀和首次出现的位置。初始化时，将前缀和为 0 的位置设为 -1。
2. 遍历数组：
   • 计算当前的前缀和。如果该前缀和已存在于哈希表中，说明找到了一个和为 0 的区间，更新最长长度。
   • 如果前缀和不存在于哈希表中，则将其加入哈希表，记录首次出现的位置。

示例分析

假设 nums = [0, 1, 0]：

1. 初始状态：hash[0] = -1
2. 遍历 nums：
   • 第 0 次循环：sum = -1（0 转换为 -1），hash[-1] = -1，首次出现，记录 hash[-1] = 0。
   • 第 1 次循环：sum = 0，此时 sum 已存在于 hash，计算 ret = 1 - (-1) = 2。
   • 第 2 次循环：sum = -1，再次找到 sum 已存在，计算 ret = 2 - 0 = 2。

最终结果为 2，即子数组 [0, 1] 或 [1, 0] 满足条件。

C++代码实现

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int, int> hash;
        hash[0] = -1; // 处理前缀和为 0 的情况
        int sum = 0, ret = 0;

        for (int i = 0; i < nums.size(); i++) {
            sum += (nums[i] == 0) ? -1 : 1; // 将 0 视为 -1，1 视为 1
            if (hash.count(sum)) 
                ret = max(ret, i - hash[sum]); // 更新最大长度
            else 
                hash[sum] = i; // 记录首次出现的位置
        }

        return ret;
    }
};

易错点提示

1. 哈希表初始化：
   • hash[0] = -1 确保能统计从起点到 i 的子数组和为 0 的情况。
2. 前缀和更新顺序：
   • 在遍历过程中，计算 sum 后先查找 hash[sum]，再更新 hash[sum]。
3. 返回值累加逻辑：
   • 计算长度时，利用哈希表中存储的前缀和位置来得到最长子数组的长度。

代码解读

通过使用哈希表存储前缀和出现的次数，我们可以在一次遍历中快速找到和为 0 的最长子数组的长度。

• 时间复杂度：O(n)，只需遍历数组一次。
• 空间复杂度：O(n)，最坏情况下，可能存储 n 个不同的前缀和。

2.4 矩阵区域和（medium）

题目链接：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) 在矩阵内。

示例 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

解法（二维前缀和）

算法思路：

• 使用二维前缀和的概念来高效计算每个 (i, j) 位置的矩阵区域和。
• 首先构造一个前缀和矩阵 dp，然后根据区域的左上角和右下角的坐标来快速获取所需的和。

1. 初始化前缀和矩阵：
   • 构造一个 (m + 1) x (n + 1) 的前缀和矩阵 dp，其中 dp[i][j] 表示 mat 矩阵中 (0,0) 到 (i-1,j-1) 的元素和。
2. 计算前缀和：
   • 遍历原矩阵 mat，根据前缀和的性质填充 dp。
3. 计算区域和：
   • 对于每个位置 (i, j)，计算左上角和右下角的坐标，然后利用前缀和矩阵快速得到区域和。

示例分析

假设 mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]，k = 1：

1. 初始化前缀和矩阵 dp：
   • 计算出 dp，其中 dp[i][j] 是对应矩阵区域的和。
2. 对于 i=1, j=1 位置：
   • 左上角坐标 (0, 0) 和右下角坐标 (2, 2)。
   • 通过 dp 计算：
     • ret[1][1] = dp[2][2] - dp[0][2] - dp[2][0] + dp[0][0]。

最终得到的矩阵区域和为 [[12, 21, 16], [27, 45, 33], [24, 39, 28]]。

C++代码实现

class Solution {
public:
    vector<vector<int>> matrixBlockSum(vector<vector<int>>& mat, int k) {
        int m = mat.size(), n = mat[0].size();
        vector<vector<int>> dp(m + 1, vector<int>(n + 1));

        // 1. 预处理前缀和矩阵
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
            }
        }

        // 2. 计算区域和
        vector<vector<int>> ret(m, vector<int>(n));
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int x1 = max(0, i - k), y1 = max(0, j - k);
                int x2 = min(m - 1, i + k), y2 = min(n - 1, j + k);
                ret[i][j] = dp[x2 + 1][y2 + 1] - dp[x1][y2 + 1] - dp[x2 + 1][y1] + dp[x1][y1];
            }
        }

        return ret;
    }
};

易错点提示

1. 边界条件：
   • 确保左上角和右下角的坐标在矩阵范围内，通过 max 和 min 函数处理。
2. 前缀和更新：
   • 在计算前缀和时，要注意从 (1,1) 开始填充，以避免越界。
3. 结果计算逻辑：
   • 注意在 dp 矩阵中使用的是 x2 + 1 和 y2 + 1，因为 dp 矩阵是多一行和多一列的。

代码解读

通过构建前缀和矩阵，可以在 O(1) 时间内计算任意区域的和，使得整个算法的时间复杂度为 O(m * n)，而空间复杂度也是 O(m * n)，适合给定的约束条件。

写在最后

前缀和作为一种高效的数据结构，极大地简化了众多数组与矩阵相关问题的求解过程。本文通过解析具体问题，如和为 k 的子数组、和可被 k 整除的子数组及最长连续数组，展示了前缀和与哈希表结合的威力。每个示例不仅提供了解法，还详细解释了代码实现的思路与易错点，帮助读者更好地理解与掌握。通过这些深入的分析，读者能够在面临复杂问题时，更自信地运用前缀和的技巧，提升解题效率。