数组-一文搞定前缀和数组

前言

  就从数组开始,以后会一直更新算法。数组有下图这些知识点与技巧。本文主要讲解其中的前缀和知识点。
数组-一文搞定前缀和数组_第1张图片

思路

  适合的场景:原始数组不会被修改,且频繁查询某个区间的累加和。
  创建一个prefixSum数组,长度比原数组nums长度多1。prefixSum[i]存储nums[0]到nums[i]的和。
  尤其要注意prefixSum与nums的坐标换算,如下图所示。

数组-一文搞定前缀和数组_第2张图片

区域和检索 - 数组不可变(一维前缀和)

leetcode第303题

数组-一文搞定前缀和数组_第3张图片

解题思路
  常规思路是通过遍历i到j。但这样时间复杂度就是O(n)。
  采用前缀和。sumRange = prefixSum[right + 1] - prefixSum[left]。注意原数组与前缀和数组的下标换算,例如nums[i]的前缀和是preSum[i + 1]。如下图所示。

数组-一文搞定前缀和数组_第4张图片

复杂度分析
  时间复杂度:初始化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题

数组-一文搞定前缀和数组_第5张图片
数组-一文搞定前缀和数组_第6张图片

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

数组-一文搞定前缀和数组_第7张图片

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

数组-一文搞定前缀和数组_第8张图片

  所以上图中紫色部分前缀和又如何求呢?答案:上图紫色部分前缀和 = 下图黄色部分前缀和 + 下图红色部分前缀和 - 重叠部分前缀和 + 原数组(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

数组-一文搞定前缀和数组_第9张图片

  所以只要求出原数组中每个位置的前缀和,就解决了本题。
复杂度分析
  时间复杂度:初始化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][c + 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];
    }
}

和为 K 的子数组

leetcode第560题

数组-一文搞定前缀和数组_第10张图片

解题思路
  
思路
  常规思路是通过双重循环遍历前缀和数组,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个元素。如下图所示。
数组-一文搞定前缀和数组_第11张图片

  2.从nums的第0项(对应前缀和数组的第1项),开始遍历。此时preSum - k = -2。map中不存在key = -2的键值对。所以此时count = 0。并将key = preSum = 1, value = 1加入map。如下图所示。
数组-一文搞定前缀和数组_第12张图片

  3.访问nums数组的第1项(对应前缀和数组的第2项)。此时preSum - k = 0。map中存在key =0的键值对,且value = 1。所以此时count = count + value = 1。并将key = preSum = 3, value = 1加入map。如下图所示。
数组-一文搞定前缀和数组_第13张图片

  4.访问nums数组的第2项(对应前缀和数组的第3项)。此时preSum - k = 3。map中存在key = 3的键值对,且value = 1。所以此时count = count + value = 2。并将key = preSum = 6, value = 1加入map。如下图所示。
数组-一文搞定前缀和数组_第14张图片

复杂度分析
  时间复杂度:O(n),其中n为数组的长度
  空间复杂度:O(n),哈希表在最坏情况下可能有n个不同的键值,因此为O(n)。
代码

class Solution {
   public int subarraySum3(int[] nums, int k) {
      HashMap 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;
   }
}

结尾

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

微信扫描下方二维码,关注公众号后回复【笔记】,有我准备的15万字Java面试笔记。

数组-一文搞定前缀和数组_第15张图片

  感谢各位人才的点赞、收藏和评论,干货文章持续更新中,下篇文章再见!

你可能感兴趣的