关于算法:数组一文搞定前缀和数组

9次阅读

共计 2956 个字符，预计需要花费 8 分钟才能阅读完成。

就从数组开始，当前会始终更新算法。数组有下图这些知识点与技巧。本文次要解说其中的前缀和知识点。

适宜的场景：原始数组不会被批改，且频繁查问某个区间的累加和。
创立一个 prefixSum 数组，长度比原数组 nums 长度多 1。prefixSum[i]存储 nums[0]到 nums[i]的和。
尤其要留神 prefixSum 与 nums 的坐标换算，如下图所示。

leetcode 第 303 题

解题思路
惯例思路是通过遍历 i 到 j。但这样工夫复杂度就是 O(n)。
采纳前缀和。sumRange = prefixSum[right + 1] - prefixSum[left]。留神原数组与前缀和数组的下标换算，例如 nums[i] 的前缀和是 preSum[i + 1]。如下图所示。

复杂度剖析
工夫复杂度：初始化 O(n)，每次检索 O(1)，n 是数组长度。
空间复杂度：O(n)。
代码

class NumArray {private int[] prefixSum;
    public NumArray(int[] nums) {prefixSum = new int[nums.length + 1];
        for (int i = 0; i < nums.length; i++) {prefixSum[i + 1] = prefixSum[i] + nums[i];
        }
    }
    public int sumRange(int left, int right) {return prefixSum[right + 1] - prefixSum[left];
    }
}

leetcode 第 304 题

解题思路
题中要求值设为下图中的红框局部，则有下图红框局部和 = 下图蓝框局部的和 – 下图绿框局部的和 – 下图黄框局部的和 + 下图灰框局部的和。

定义原二维数组的前缀和数组为 preSum。则 preSumi 示意原数组中 (0, 0) 坐标与 (i – 1, j – 1) 坐标组成的矩形区域的和，如下图所示，紫色框对应的前缀和为 17。
这里须要留神原数组与前缀和数组的坐标换算。比方原数组坐标为 (i – 1, j – 1)，则在前缀和数组中的坐标为(i, j)。
而下面一开始提到的蓝框的和，绿框的和，黄框的和，灰框的和的求法都一样。也就是对应地位二维数组的前缀和。

所以上图中紫色局部前缀和又如何求呢？答案：上图紫色局部前缀和 = 下图黄色局部前缀和 + 下图红色局部前缀和 – 重叠局部前缀和 + 原数组 (i – 1, j – 1) 地位的值，即preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1] = 9 + 14 - 8 + 2 = 17。

所以只要求出原数组中每个地位的前缀和，就解决了本题。
复杂度剖析
工夫复杂度：初始化 O(rc)，每次检索 O(1)，其中 r 与 c 别离为 matrix 的行数和列数。
空间复杂度：O(rc)。
代码

class NumMatrix {private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        int r = matrix.length;
        if (r == 0) {return;}
        int c = matrix[0].length;
        if (c == 0) {return;}
        preSum = new int[r + 1];
        for (int i = 1; i <= r; i++) {for (int j = 1; j <= c; j++) {preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
    }
}

leetcode 第 560 题

解题思路

思路
惯例思路是通过双重循环遍历前缀和数组，j < i，若当preSum[j] + k == preSum[i] 时，阐明数组从 j – 1 到 i 的和为 k，则 count++。但这样工夫复杂度就是 O(n^2)。
采纳 HashMap + 前缀和数组形式，工夫复杂度可达到 O(n)。
由 preSum[j] + k == preSum[i] 移项得 preSum[j] == preSum[i] - k。所以只有统计有多少个前缀和为 preSum[i] – k 即能够统计出有多少个子串的和为 k。
建设 map，其中 key=preSum[i]，value= 满足 preSum[i] – k 的 preSum[j] 有多少个（有多少个满足，就代表有多少个子串的和为 k），其中必须 j < i。

示例
示例 nums = [1,2,3]，k = 3。流程如下。
1. 因为不会当时构建前缀和数组，所以此处先增加前缀和的第 0 个元素。如下图所示。

2. 从 nums 的第 0 项（对应前缀和数组的第 1 项），开始遍历。此时 preSum – k = -2。map 中不存在 key = - 2 的键值对。所以此时 count = 0。并将 key = preSum = 1，value = 1 退出 map。如下图所示。

3. 拜访 nums 数组的第 1 项（对应前缀和数组的第 2 项）。此时 preSum – k = 0。map 中存在 key = 0 的键值对，且 value = 1。所以此时 count = count + value = 1。并将 key = preSum = 3，value = 1 退出 map。如下图所示。

4. 拜访 nums 数组的第 2 项（对应前缀和数组的第 3 项）。此时 preSum – k = 3。map 中存在 key = 3 的键值对，且 value = 1。所以此时 count = count + value = 2。并将 key = preSum = 6，value = 1 退出 map。如下图所示。

复杂度剖析
工夫复杂度：O(n)，其中 n 为数组的长度
空间复杂度：O(n)，哈希表在最坏状况下可能有 n 个不同的键值，因而为 O(n)。
代码

class Solution {public int subarraySum3(int[] nums, int k) {HashMap<Integer, Integer> map = new HashMap<>();
      // 初始状况，因为此处没有应用前缀和数组，因而须要先将前缀和为 0 的，呈现了 1 次的的状况记录在 map 外面，也就是前缀数组中的第 0 项
      map.put(0, 1);
      int count = 0, sum0i = 0;
      for (int i = 0; i < nums.length; i++) {sum0i += nums[i];
         count += map.getOrDefault(sum0i - k, 0);
         // 以下两句代码，必须在以上两句代码的后边，这样变相保障了 j < i
         int c = map.getOrDefault(sum0i, 0);
         map.put(sum0i, ++c);
      }
      return count;
   }
}

好了数组中的前缀和技巧就讲这三道。下一篇算法文章讲差分数组。