Eighteen Blog

题目说明

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
给定一个整数数组 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]


提示:

1 <= A.length <= 30000
-10000 <= A[i] <= 10000
2 <= K <= 10000

解题思路一(暴力枚举,O(n^3))

  1. 暴力枚举所有的前序和,判断对K取模是否为0,为0则结果+1

    代码实现一

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    /**
    * @param {number[]} A
    * @param {number} K
    * @return {number}
    */
    var subarraysDivByK = function(A, K) {
    let res = 0;
    for (let i = 0; i < A.length; i++) {
    let prev = 0;
    for (let j = i; j >= 0; j--) {
    prev += A[j];
    if (prev % K === 0) {
    res++
    }
    }
    }
    return res;
    };

解题思路二(暴力枚举优化,O(n^2))

  1. 将两层for循环中的求前序和操作,提前求。
  2. 那么我们求i之前的所有前序和就变成了,求p[i] - p[j] (j的范围是 0 ~ i-1)
  3. 判断p[i] - p[j]对K去模是否为0,为0则结果+1

    代码实现二

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    /**
    * @param {number[]} A
    * @param {number} K
    * @return {number}
    */
    var subarraysDivByK = function(A, K) {
    let res = 0;
    let p = new Array(A.length);
    for (let i = 0; i < A.length; i++) {
    p[i] = A.slice(0, i+1).reduce((sum, item, key, arr) => {
    return sum += item;
    }, 0);
    for( let j = i - 1; j >= 0; j--) {
    if((p[i] - p[j]) % K === 0) {
    res++
    }
    }
    if(p[i] % K === 0) {
    res++
    }
    }
    return res;
    };

解题思路三(同余定理,O(n))

先理解一个数学问题, 假设a = 8,b = 13, 同时mod 5,那么 a % 5 == 3,b % 5 == 3,即a % 5 == b % 5(b - a) % 5 == 0即对同一数取模相同的两个值,其差值可整除该数。

  1. 将两层for循环中的求前序和操作,提前求前序和序列p。
  2. 得到所有的前序和p之后,理解说明若 p[i] % K === p[j] % Kp[i] - p[j] % 5 === 0那么ji就是我们求的一个目标子序列。
  3. 所以我们建立一个hash,用来存储p序列取模之后的值。 hash的键值范围是(0 ~ K -1)因为是对K取余,所以值只可能出现在该范围中。
  4. 由于该hash的标记跟数组下标正好对应,所以hash就声明为一个数组。
  5. 以示例为例
    1. 输入:`A = [4,5,0,-2,-3,1], K = 5`
    2. p序列为  `[4, 9, 9, 7, 4, 5]` 取模之后的序列为`[4, 4, 4, 2, 4, 0]` 记录到hash中
    3. hash = `[1, 0, 1, 0, 4]` 
    4. 接下来就是排列组合的问题了,将hash列表中 `> 1` 的值进行计算 `n * ( n - 1 ) / 2` 取和
    5. 最后再加上`hash[0]`的个数,因为`hash[0]`标记的是取模之后为`0`的值的个数,本身就属于目标子序列。
    
  6. 第五步我们是先求出hash表才计算个数,我们也可以在完善hash的同时计算。
    1. 比如p序列为 [4, 9, 9, 7, 4, 5] 去模的过程中统计。
    2. 计算第1个取模,模值为4,res += hash[4], hash[4]++,由于4是第1次出现所以目前res+=0
    3. 计算第2个取模,模值为4,res += hash[4], hash[4]++,由于4是第2次出现所以目前res+=1,子序列下标范围是[0,1]
    4. 计算第3个取模,模值为4,res += hash[4], hash[4]++,由于4是第3次出现所以目前res+=2,子序列下标范围是[0,1,2],[1,2]因为4出现3次,所以第3个4可以和前两个组合。
    5. 依次类推。

代码实现三

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
* @param {number[]} A
* @param {number} K
* @return {number}
*/
var subarraysDivByK = function(A, K) {
let hash = new Array(K).fill(0);
let sum = 0;
let res = 0;
for (let i = 0; i < A.length; i++) {
sum += A[i];
let key = sum % K;
key = key < 0 ? (key + K) : key; //处理负数的情况, (3 - (-2)) % 5 === 0
res += hash[key];
hash[key]++;
}
return res + hash [0];
};

 评论