@Yano 2019-01-13T15:46:32.000000Z 字数 1336 阅读 1550

# 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


# 代码

## 半暴力解法（超时）

public int subarraysDivByK(int[] A, int K) {    int[] sum = new int[A.length];    for (int i = 0; i < A.length; i++) {        sum[i] = (i == 0 ? 0 : sum[i - 1]) + A[i];    }    int ans = 0;    if (sum[0] % K == 0) ans++;    for (int i = 1; i < sum.length; i++) {        if (sum[i] % K == 0) ans++;        for (int j = i - 1; j >= 0; j--) {            int tmp = sum[i] - sum[j];            if (tmp % K == 0) {                ans++;            }        }    }    return ans;}

## AC解法

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


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


public int subarraysDivByK(int[] A, int K) {    int mod[] = new int[K];    int cumSum = 0;    for (int i = 0; i < A.length; i++) {        cumSum += A[i];        // countSum % K 可能是负数，需要 +K        mod[((cumSum % K) + K) % K]++;    }    int ans = 0;    for (int i = 0; i < K; i++) {        if (mod[i] > 1) {            ans += (mod[i] * (mod[i] - 1)) / 2;        }    }    ans += mod[0];    return ans;}

• 私有
• 公开
• 删除