时间戳

首页 > 技术文章 > LeetCode“前缀和”系列（1）——第974题详解

LeetCode“前缀和”系列（1）——第974题详解

SupremeBoy 2020-05-27 22:11 原文

一、什么是“前缀和”？

前缀和就是数组第0项到当前项的和。如果用一个数组preSum表示数组A的前缀和：

preSum[i]=A[0]+A[1]+...+A[i];

数组A中的某项，可以表示为相邻前缀和之差：

A[i]=preSum[i]-preSum[i-1]

多项叠加，等号右边加减相消，得到通式：

A[i]+…+A[j]=preSum[j]−preSum[i−1]

i 当然可以为 0，此时 i - 1 为 - 1，我们故意让 preSum[-1] 为 0，此时：

A[0]+A[1]+…+A[j]=preSum[j]

预置这种不存在的情况，只是为了让 preSum[0]preSum[0] 能套用通式。

二、问题描述

给定一个整数数组 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]

三、问题等价转换

子数组的元素之和=>数组第i项到第j项的和

元素和能被K整除的子数组数目=>有几种i，j组合，使得A[i]到A[j]之和mod K==0

转化为：

  • 有几种 i、j组合，满足 (preSum[ j ] - preSum[ i - 1 ])mod K== 0
  • 有几种 i、j组合，满足 preSum[j] mod K == preSum[i-1] mod K
  • 前提：preSum[j]preSum[j] 、preSum[i-1]preSum[i−1] 为正整数。负数的情况要处理

前缀和数组 preSum 的项怎么求？

  • 当前项的前缀和 = 上一项的前缀和 + 当前项
  • 求出的 preSum 数组项，让它 mod K，mod 完再看哪两项相等，计数
  • 通式有 i、j两个变量，找出数组中所有相等的两项，需要 2 层循环去遍历 i,j
  • 时间复杂度：O(n^2) 。 我们希望继续优化

我们只关心什么：数值和频次，降低时间复杂度

  • 前缀和与数组A的项一一对应，但我们不关心它具体对应到哪一项
  • 我们只关心出现过哪些 【前缀和 mod K】 数值，和对应的出现次数
  • 用一个变量 preSumModK ，保存每次求出的 前缀和 mod K，存入哈希表
  • 存键值对：
    • key：前缀和 mod K 。数值 作为 key
    • value：这个结果值出现了几次
  • 前缀和 mod K 的值正好是 0,1,2...,K-1，恰似索引，所以也可以用数组存，代码见最后

找到 preSumModK 的递推关系，用于迭代计算

  • mod 的分配率： (a + b) mod c = (a mod c + b mod c) mod c
  • 当前的 preSumModK

　　　　= (当前的前缀和) mod K
　　　　= (上一项的前缀和 + A[i]) mod K
　　　　= ((上一项的前缀和) mod K + A[i] mod K ) mod K
　　　　= (上一个 preSumModK + A[i] mod K ) mod K
　　　　= (上一个 preSumModK + A[i] ) mod K

  • 一前一后的 preSumModK 有了联系，便可在迭代中计算它

整个流程过一遍

  • 预置 preSum[-1] = 0
    • -1 代表数组 A 的第 -1 项，即遍历数组 A 之前，map 提前放入 0:1，表示 求第 0 项前缀和之前，前缀和 mod K 等于 0 已经出现了 1 次
    • 这是违背现实的，但别纠结，只是为了求出第一个 preSumModK 而已
  • 遍历数组 A 的每一项，求当前项的 preSumModK ，存入 map 中
    • 之前没有存过，则作为 key 存入，值为 1
    • 之前存过，则对应值 +1
    • 于是 map 就录入了各项对应的【前缀和 mod K】
  • 边存 边查看已有的 key ，如果 map 中存在 key 等于 当前 preSumModK
    • 说明存在 之前求过的 preSumModK ，等于 当前 preSumModK
    • 把 key 对应的出现次数，累加给 count
    • 过去的某个前缀和，与当前前缀和搭配，差分出一个子数组
    • 出现过几次 ，就是有几个过去的前缀和，与当前前缀和，差分出几个满足条件的子数组

尝试一句话概括

  • 根据 当前前缀和 mod K，在哈希表中找到与之 相等 的 key 。满足条件的 历史preSumModK 出现过 n 次，就是当前 前缀和 能找到 n 个历史前缀和，与它组合搭配，形成 n 个不同的子数组，满足元素和能被 K 整除
  • 遍历数组 A 每一项，重复以上步骤， n 不断累加给 count，最后返回 count

算法复杂度

  • Time：O(n)
  • Space：O(K)。 mod 的结果最多 K 种，哈希表最多存放 K 个键值对

补充：前缀和 为负数 的情况

  • 举例：K = 4，求得一个前缀和为 -1 ， -1 % K = -1 ，3 % K = 3
  • 看似模的结果不相等，一个为 -1 一个为 3 ，但它们应该记到一组
  • 因为它们前缀和之差：3 - (-1) 为 4 。 4 % K = 0
  • 所以 mod K 的结果 -1 ，要加上 K ，转成正数的 3

代码实现

1、暴力法

    // 暴力方法，最后超时间限制
    public static int subarraysDivByK1(int[] A, int K) {
        int ans=0;
        for (int i = 0; i < A.length; i++) {
            int sum=0;
            for (int j = i; j < A.length; j++) {
                sum+=A[j];
                if(sum%K==0) ans++;
            }
        }

        return ans;
    }

2、使用哈希表的代码

// 前缀法
    public static int subarraysDivByK2(int[] A, int K) {
        int ans=0;
        Map<Integer,Integer> map=new HashMap<>();
        map.put(0,1);
        int preSumModK=0;

        for (int i = 0; i < A.length; i++) {
            preSumModK=(preSumModK+A[i])%K;
            if(preSumModK<0) preSumModK+=K;

            if(map.containsKey(preSumModK)){
                int temp=map.get(preSumModK);
                ans+=temp;
                map.put(preSumModK,temp+1);
            }
            else {
                map.put(preSumModK,1);
            }
        }
        return ans;
    }

3、使用数组

// 前缀法，数组代替哈希表
    public static int subarraysDivByK3(int[] A, int K) {
        int ans=0;
        int []map=new int[K];
        map[0]=1;
        int preSumModK=0;

        for (int value : A) {
            preSumModK = (preSumModK + value) % K;
            if (preSumModK < 0) preSumModK += K;

            int temp = map[preSumModK];
            if (temp != 0) {
                ans += temp;
                map[preSumModK] = temp + 1;
            } else {
                map[preSumModK] = 1;
            }
        }

        return ans;
    }

参考资料：
链接：https://leetcode-cn.com/problems/subarray-sums-divisible-by-k/solution/you-jian-qian-zhui-he-na-jiu-zai-ci-dai-ni-da-tong/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

推荐阅读