[关闭]
@Yano 2019-01-13T07:46:32.000000Z 字数 1336 阅读 977

LeetCode 974 Subarray Sums Divisible by K

LeetCode


题目描述

Given an array A of integers, return the number of (contiguous, non-empty) subarrays that have a sum divisible by K.

Example 1:

Input: A = [4,5,0,-2,-3,1], K = 5
Output: 7
Explanation: There are 7 subarrays with a sum divisible by K = 5:
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

Note:

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

代码

半暴力解法(超时)

定义一个sum[]数组,sum[i]=sum(A[0], A[1], ... A[i])。

对于每一个i,都从计算sum[i]~sum[A.length - 1]是否能够被K整除。

时间复杂度:O(n^2)
空间复杂度:O(n)

解法超时。本题规定了A[i]的大小,实际上sum还有溢出的风险。

  1. public int subarraysDivByK(int[] A, int K) {
  2. int[] sum = new int[A.length];
  3. for (int i = 0; i < A.length; i++) {
  4. sum[i] = (i == 0 ? 0 : sum[i - 1]) + A[i];
  5. }
  6. int ans = 0;
  7. if (sum[0] % K == 0) ans++;
  8. for (int i = 1; i < sum.length; i++) {
  9. if (sum[i] % K == 0) ans++;
  10. for (int j = i - 1; j >= 0; j--) {
  11. int tmp = sum[i] - sum[j];
  12. if (tmp % K == 0) {
  13. ans++;
  14. }
  15. }
  16. }
  17. return ans;
  18. }

AC解法

其实上面的解法已经很接近了,但是思考一下为什么会超时?比如K=5,当sum[0]=4时,后面的sum[i]=5*n + 4都符合要求,即不需要判断每个和,只需要判断sum[i]%5的值就好了。

假设:

sum[i]=p*K+ri
sum[j]=q*K+rj

则:

sum[j]-sum[i]=(q-p)*K+rj-ri

若想sum[j]-sum[i]被K整除,只需要rj-ri能够被K整除即可,因为rj和ri都是对K的模,所以只要rj=ri即可。

所以这道题就变成了求对K的每个模的个数,然后对于每个0~i,分别两两组合,假设mod[i]=n,那么其i的个数为n*(n-1)/2.

时间复杂度:O(n)
空间复杂度:O(K)

  1. public int subarraysDivByK(int[] A, int K) {
  2. int mod[] = new int[K];
  3. int cumSum = 0;
  4. for (int i = 0; i < A.length; i++) {
  5. cumSum += A[i];
  6. // countSum % K 可能是负数,需要 +K
  7. mod[((cumSum % K) + K) % K]++;
  8. }
  9. int ans = 0;
  10. for (int i = 0; i < K; i++) {
  11. if (mod[i] > 1) {
  12. ans += (mod[i] * (mod[i] - 1)) / 2;
  13. }
  14. }
  15. ans += mod[0];
  16. return ans;
  17. }
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注