区块链技术博客
www.b2bchain.cn

前缀和

这篇文章主要介绍了前缀和,通过具体代码讲解6058并且分析了前缀和的详细步骤与相关技巧,需要的朋友可以参考下

本文实例讲述了前缀和。分享给大家供大家参考文章查询地址https://www.b2bchain.cn/?p=6058。具体如下:

算法

算法

发布日期:   2020-03-26
文章字数:   3k
阅读时长:   13 分
阅读次数:  

前缀和

最近刷了几个前缀和的题,也都是板子题,记录一下

LeetCode 560. 和为K的子数组

给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

输入:nums = [1,1,1], k = 2 输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

说明 :

  1. 数组的长度为 [1, 20,000]。
  2. 数组中元素的范围是 [-1000, 1000] ,且整数 k 的范围是 [-1e7, 1e7]。

这个题直接前缀和就能过,下面一种不好的暴力求法,虽然能过,但是巨慢

    public static int subarraySum(int[] nums, int k) {         int n = nums.length;         int[] ps = new int[n + 1];         for (int i = 1; i <= n; i++) {             ps[i] = nums[i - 1] + ps[i - 1];         }         int res = 0;;         for (int s = 0; s < n; s++) {             for (int e = s + 1; e <= n; e++) {                 if (ps[e] - ps[s] == k) {                     res++;                 }             }         }         return res;     }

但实际上,我们要看ps[j] - ps[i] = k,那么[i,j]就是我们需要的区间,所以我们对于每个j,我们只要计算有多少个 i 使得 ps[j] - ps[i] = k,这样我们就得到了以 P[j] 作为右区间并且和为 k的区间数。这里用个 hashmap 统计 ps[i] 即可。但是要注意初始化map的细节,要放一个{0:1}进去,当 ps[j]==k 时,ps[i]=0 ,此时是要算进结果的

    public static int subarraySum(int[] nums, int k) {         int res = 0;         int curSum = 0;         HashMap<Integer, Integer> map = new HashMap<>();         map.put(0, 1);         for (int i = 0; i < nums.length; i++) {             curSum += nums[i];             if (map.containsKey(curSum - k)) {                 res += map.get(curSum - k);             }             map.put(curSum, map.getOrDefault(curSum, 0) + 1);         }         return res;     }

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

给定一个整数数组 A,返回其中元素之和可被 K 整除的(连续、非空)子数组的数目。

示例:

输入:A = [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]

这个题,暴力前缀和就不合适了,有什么好的方法呢?

我们要判断的是(ps[j] - ps[i]) % K是否等于0。那么根据取余的性质,(ps[j] - ps[i]) % K = ps[j] % K - ps[i] % K,所以,若要(ps[j] - ps[i] )% K = 0只要 ps[j] % K = ps[i] % K,以ps[i] % K作为键值统计其出现的频率,从而对于每个下标 j 我们可以立即获得能和它组成满足要求的子数组的开始下标 i 的数量。生成前缀和数组的过程中,将 key = ps[j]% k 出现的频率加入结果数组, 同时将 key = ps[j] % k 的出现频率加1。

由于数组中有可能出现负数,需要将其加 K ,使其 %K 之后的值为正数。

    public int subarraysDivByK(int[] A, int k){         int n = A.length, res = 0, sum = 0;         int[] map = new int[k];         map[0] = 1;         for (int i = 0; i < n; i++) {             sum += A[i];             int key = (sum % k + k) % k;             //在加进去前先统计下数量             res += map[key];             map[key]++;         }         return res;     }
class Solution:     def subarraysDivByK(self, A: List[int], K: int) -> int:         n, res, sum, dict = len(A), 0, 0, collections.defaultdict(int)         dict[0] = 1         for i in range(n):             sum += A[i]             key = (sum % K + K) % K             res += dict[key]             dict[key] += 1         return res

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

给出矩阵 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 子矩阵。

提示:

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

这个题,一看就是二维前缀和,所谓二维前缀和就是,对于每一行从前向后累加,对于每一列从前向后累加,得到的矩阵就是前缀和矩阵。

当我们构建好了二维前缀和,想要求 (i1,j1) 为左上角,(i2,j2) 为右下角的矩阵的内部和的时候,是这么一张图。要求 S4,实际上就是(S1+S2+S3+S4),也就是 S(0,0,i2,j2),这么一整块大的,减去 S2+S1 ,减去 S3+S1 ,再加上 S1。因为单个的 S2S3 我们是不好算的,但是S1+S2S1+S3是很好算的。

前缀和

如果直接莽,那时间复杂度是 $O(n^2 * m^2)$,需要继续优化,这个题和 560题 差不多吧,之前是一维问题,现在是二维问题,但是处理思想是一样的。要将二维转化为一维,此时我们只要计算每一行的前缀和,而不是整个矩阵的前缀和。然后可以取不同的两个列 (j1,j2),以这两个列为边界,计算每一行的前缀和,这就是二维前缀和。

那么我们固定好左右边界后,遍历每一行,记录每一行的前缀和,以及它出现的次数,放在map中,那么对于当前行的前缀和,我们只要看map里有没有curSum - target,有的话加上它的出现次数即可。

注意,map初始化也要放入{0:1}

java 代码

    public int numSubmatrixSumTarget(int[][] mat, int target) {         int n = mat.length;         int m = mat[0].length;          for (int i = 0; i < n; i++) {             for (int j = 1; j < m; j++) {                 mat[i][j] += mat[i][j - 1];             }         }         int res = 0;         int cur = 0;         Map<Integer, Integer> map = new HashMap<>();         //枚举两列         //第i列         for (int j1 = 0; j1 < m; j1++) {              //第j列             for (int j2 = j1; j2 < m; j2++) {                 map.clear();                 //矩阵为空的情况                 map.put(0, 1);                 cur = 0;                 //枚举行数                 for (int i = 0; i < n; i++) {                     cur += mat[i][j2] - (j1 > 0 ? mat[i][j1 - 1] : 0);                     res += map.getOrDefault(cur - target, 0);                     map.put(cur, map.getOrDefault(cur, 0) + 1);                 }             }         }         return res;     }

python 代码

class Solution:     def numSubmatrixSumTarget(self, mat: List[List[int]], target: int) -> int:         res, n, m = 0, len(mat), len(mat[0])         # 首先计算每行的前缀和         for i in range(n):             for j in range(1, m):                 mat[i][j] += mat[i][j - 1]          # 枚举两列         for j1 in range(m):             for j2 in range(j1,m):                 dict = collections.defaultdict(int)                 dict[0] = 1                 cur_sum = 0                 # 枚举每一行                 for i in range(n):                     cur_sum += mat[i][j2] - (mat[i][j1 - 1] if j1 > 0 else 0)                     res += dict[cur_sum - target]                     dict[cur_sum] += 1          return res

LeetCode 363. 矩形区域不超过 K 的最大数值和

给定一个非空二维矩阵 matrix 和一个整数 k,找到这个矩阵内部不大于 k 的最大矩形和。

示例:

输入: matrix = [[1,0,1],[0,-2,3]], k = 2 输出: 2  解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2,且 2 是不超过 k 的最大数字(k = 2)。

说明:

  1. 矩阵内的矩形区域面积必须大于 0。
  2. 如果行数远大于列数,你将如何解答呢?

这个题就和上一个题太像了,几乎一致,1074 是找面积等于 k 的,这个题是找小于等于k 的最大矩形和,但是也没给数据范围,直接莽的话 $ O(n^2 * m^2)$吧,不太合适,还是要转成先求行的前缀和,再枚举两列、枚举行来求,固定左右边界,只考虑行,在哪两个行之间组成矩形的面积最大。如果是和1074一样用map的话,我怎么找到当前情况下,某个值 + curSum <= k?直接遍历,那就不好了,为了加快查找!那么这里就要用到 TreeSetceiling() 了,之前在 300 题也用过,ceiling() 方法返回的是大于这个值的最小值,如果不存在返回null。

set 保存之前的子矩阵的和 sum,然后在 set 中找出大于等于(sum - k)的最小值。set中都是存放的是起始列和中止列相同的矩阵的和,求出 set 中大于等于(curSum - k)最小值,设找到的数为 c,则 c >= cur-k,必有 cur - c <= k,所有最小的 c,使得 cur-c的值最大,且该值小于等于k,妙啊

java 代码

    public int maxSumSubmatrix(int[][] mat, int k) {         int n = mat.length;         int m = mat[0].length;         //首先计算每一行的前缀和         for (int i = 0; i < n; i++) {             for (int j = 1; j < m; j++) {                 mat[i][j] += mat[i][j - 1];             }         }         int res = 0x80000000;         TreeSet<Integer> set = new TreeSet<>();         // 枚举j1列         for (int j1 = 0; j1 < m; j1++) {             // 枚举j2列             for (int j2 = j1; j2 < m; j2++) {                 set.clear();                 set.add(0);                 int curSum = 0;                 int curMax = 0x80000000;                 // 枚举每一行                 for (int i = 0; i < n; i++) {                     curSum += mat[i][j2] - (j1 > 0 ? mat[i][j1 - 1] : 0);                     System.out.println(curSum);                     Integer c = set.ceiling(curSum - k);                     if (c != null) {                         curMax = Math.max(curMax, curSum - c);                     }                     set.add(curSum);                 }                 res = Math.max(res, curMax);                 System.out.println();             }             System.out.println();         }         return res;     }

python 代码

class Solution:     def maxSumSubmatrix(self, mat: List[List[int]], k: int) -> int:         import bisect         n, m, res = len(mat), len(mat[0]), float('-inf')         # 首先计算每一行前缀和         for i in range(n):             for j in range(1, m):                 mat[i][j] += mat[i][j - 1]          # 枚举列1         for j1 in range(m):             # 枚举列2             for j2 in range(j1,m):                 cur_sum,arr = 0,[0]                  # 枚举每一行                 for i in range(n):                     cur_sum += mat[i][j2] - (mat[i][j1 - 1] if j1 > 0 else 0)                     loc = bisect.bisect_left(arr,cur_sum - k)                     # 如果能找到                     if loc < len(arr):                         res = max(res,cur_sum - arr[loc])                     bisect.insort(arr,cur_sum)         return res

1292. 元素和小于等于阈值的正方形的最大边长

给你一个大小为 m x n 的矩阵 mat 和一个整数阈值 threshold。请你返回元素总和小于或等于阈值的正方形区域的最大边长;如果没有这样的正方形区域,则返回 0

示例 1:

前缀和

输入:mat = [[1,1,3,2,4,3,2],[1,1,3,2,4,3,2],[1,1,3,2,4,3,2]], threshold = 4 输出:2 解释:总和小于 4 的正方形的最大边长为 2,如图所示。

提示:

1 <= m, n <= 300 m == mat.length n == mat[i].length 0 <= mat[i][j] <= 10000 0 <= threshold <= 10^5

第167场周赛题,和前面题基本上一样,只不过这里不是矩形,变成了正方形。依然是利用前缀和+二分的思想。直接算二维前缀和。

比如我现在要计算坐标为(i,j)的二维前缀和,就要利用到它左边的前缀和和上边的前缀和,如图所示,左边那块 $sum[i][j-1]$(粉色)和上面那块 $sum[i-1][j]$(紫色),这两个前缀和加起来,再减去共同区域 $sum[i-1][j-1]$,最后加上这个点的值 $mat[i-1][j-1]$(这里开的都是n+1,下标从1开始) ,那就是 $sum[i][j]$

前缀和

sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + A[i-1][j-1] (sum比A的行和列都多开一维)

当我们要计算某块区域元素内的和

int val = sum[i][j] - sum[i][j-k] - sum[i-k][j] +sum[i-k][j-k],k代表区间的长度(以正方形为例)

前缀和

Java 代码

public int maxSideLength(int[][] mat, int threshold) {         int n = mat.length;         int m = mat[0].length;         int[][] sum = new int[n + 1][m + 1];         //计算二维前缀和         for (int i = 1; i <= n; i++) {             for (int j = 1; j <= m; j++) {                 sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + mat[i - 1][j - 1];             }         }         // for (int i = 0; i <= n; i++) {         //     for (int j = 0; j <= m; j++) {         //         System.out.print(sum[i][j] +" ");         //     }         //     System.out.println();         // }          //二分找答案         int start = 0;         int end = Math.min(n, m) ;         while (start + 1 < end) {             int mid = start + (end - start) / 2;             if (valid(sum, mid, threshold)) {                 start = mid;             } else {                 end = mid;             }         }          //double check         if (valid(sum, end, threshold)) {             return end;         } else {             return start;         }     }      private static boolean valid(int[][] sum, int len, int threshold) {         // 枚举正方形右下角         for (int i = len; i < sum.length; i++) {             for (int j = len; j < sum[0].length; j++) {                 int temp = sum[i][j] - sum[i - len][j] - sum[i][j - len] + sum[i - len][j - len];                 if (temp <= threshold) {                     return true;                 }             }         }         return false;     }


算法

前缀和最近刷了几个前缀和的题,也都是板子题,记录一下 LeetCode 560. 和为K的子数组 给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。 示例 1 : 输入:nums = [1,1,1], k =
2020-03-26 算法
程序员修炼之道读书笔记补上前言 一直有个读书的计划,每一年都是懒过去了,白稚卿说的很对,能战胜懒的只有ddl和绝对的自律,在学校里也只有老师要求写读书笔记才会去翻阅一下了,在学校各种压力都很大,大家选择解压的方式各不相同,我也开始尝试读一些
2020-03-19 随笔

本文地址https://www.b2bchain.cn/?p=6058

赞(0) 打赏
部分文章转自网络,侵权联系删除b2bchain区块链学习技术社区 » 前缀和
分享到: 更多 (0)

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址

b2b链

联系我们联系我们