题目描述

给定一个整数数组 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. 1 <= A.length <= 30000
  2. -10000 <= A[i] <= 10000
  3. 2 <= K <= 10000

思路

求组合数1+2+3+...+n=(1+n)*n/2

代码

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] map = new int[k];
        map[0] = 1;
        int preSum = 0;
        int ans = 0;
        for (int num : nums) {
            preSum = (preSum + num) % k;
            if (preSum < 0) { preSum += k; }
            ans += map[preSum]++;
        }
        return ans;
    }
}

class Solution {
    public int subarraysDivByK(int[] A, int K) {
        int[] dp = new int[K];  // 要么除K = 0, 只有当两个都是在里面的时候才进行加入
        int count = 0;
        int t = 0;
        int ans = 0;
        int i;
        for (i = 0; i < A.length; i++)
        {
            count += A[i];
            if (count % K < 0)
            {
                t = count % K + K;
            }
            else t = count % K;
            if (t == 0)
            {
                dp[0] += 1;
                ans += dp[0];
            }
            else if (t != 0 && dp[t] == 0)
            {
                dp[t] = 1;
            } 
            else if (t != 0)
            {
                ans += dp[t];
                dp[t] += 1;
            }
        }
        return ans;
    }
}

提交


题后