【LeeCode】974. 和可被 K 整除的子数组

【题目描述】

给定一个整数数组 ​​nums​​​ 和一个整数 ​​k​​​ ，返回其中元素之和可被 ​​k​​ 整除的（连续、非空） 子数组 的数目。

子数组 是数组的 连续 部分。

​​​​https://leetcode.cn/problems/subarray-sums-divisible-by-k/​​

【示例】

【代码】admin

代码应该没有问题, 但是【超出时间限制】

 思路: 正常的叠加然后求和进行求余运算 (sum % k)==0

​ 注意：负数求余为0 所以要多一层计算 (sum % k + k )% k == 0)

package com.company;
// 2023-03-04
import java.util.*;

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int len = nums.length;

        int res = 0;
        for (int i = 0; i < len; i++){
            int sum = 0;
            for (int j = i; j >= 0; j--){
                sum += nums[j];
                if (sum % k == 0 ||(sum % k + k ) % k == 0){
                    res++;
                }
            }
        }
        System.out.println(res);
        return res;
    }
}
public class Test {
    public static void main(String[] args) {
        new Solution().subarraysDivByK(new int[]{4,5,0,-2,-3,1}, 5);   // 输出: 5
        new Solution().subarraysDivByK(new int[]{5}, 9);   // 输出: 5
    }
}

【代码】​​哈希表 + 逐一统计​​

package com.company;
// 2023-03-04
import java.util.*;

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int len = nums.length;
        int res = 0;
        Map<Integer, Integer> map = new HashMap<>();
        // 余数为0的情况
        map.put(0, 1);

        int count = 0;
        int sum = 0;

        for (int i = 0; i < len; i++){
            // 前缀和
            sum += nums[i];
            int tmp = (sum % k + k) % k;
            // map保存余数的
            count = map.getOrDefault(tmp, 0);
            res += count;
            map.put(tmp, count + 1);
        }

        System.out.println(map);
        System.out.println(res);
        return res;
    }
}

public class Test {
    public static void main(String[] args) {
        new Solution().subarraysDivByK(new int[]{4,5,0,-2,-3,1}, 5);   // 输出: 5
        new Solution().subarraysDivByK(new int[]{5}, 9);   // 输出: 5
    }
}

【代码】很巧妙

Math.floorMod(sum, k)