MarsCode青训营打卡Day6（2025年1月19日）|稀土掘金-360.可被K整除的子数组问题

资源引用：

360.可被K整除的子数组问题

今日小记：

周末了，稍微摸个鱼，带来一道与88.连续子串和的整除问题极为相似而略有不同的哈希法题目。

稀土掘金-360.可被K整除的子数组问题（360.可被K整除的子数组问题）

题目分析：

给定一个整数数组nums和一个整数k，请找出数组中所有元素之和可以被k整除的非空连续子数组的数目。

解题重点：

使用哈希表结合前缀和思想解决问题。

前缀和prefitSum[i]的定义为从第0个元素到第i个元素的元素之和，

由此可得任意的[i,j]区间的连续子数组之和可表示为prefitSum[j] - prefitSum[i]，

故对于前缀和为prefitSum的当前连续子数组，若其对k取模的结果为mod，则只需向前寻找对k取模的结果同样为mod的其他前缀和，二者做差所得的连续子数组的元素之和显然对k取模为0，即能被k整除。

注意：由于数组元素可能为负，需要处理对前缀和为负时的取余结果。

解题思路：

1. 构造一个prefitSum用于记录前缀和，初始化一个HashMap用于记录已遍历的前缀和对k取模所得的mod及其频次，以及初始化一个res用于记录符合条件的非空连续子数组的数目
2. 遍历数组nums，

1. 1. 计算其前缀和prefitSum
   2. 对prefitSum取k的模得到mod，并处理可能存在的负数mod
   3. 若mod为0，则当前前缀和对应的连续子数组本身就符合条件，res++
   4. 从HashMap中查询mod的频次，将其加到res上
   5. 更新HashMap中mod的频次，即加一

1. 最终返回res

import java.util.Arrays;
import java.util.Map;
import java.util.HashMap;

public class Main {
    public static int solution(int[] nums, int k) {
        int res = 0;
        int prefitSum = 0;
        Map<Integer, Integer> count = new HashMap<>();
        for (int num : nums) {
            prefitSum += num;
            int mod = prefitSum % k;
            if (mod < 0) mod = k + mod;

            if (mod == 0) res++;

            res += count.getOrDefault(mod, 0);

            count.put(mod, count.getOrDefault(mod, 0) + 1);
        }
        return res; // Placeholder return
    }

    public static void main(String[] args) {
        System.out.println(solution(new int[]{4, 5, 0, -2, -3, 1}, 5) == 7 ? 1 : 0);
        System.out.println(solution(new int[]{1, 2, 3}, 3) == 3 ? 1 : 0);
        System.out.println(solution(new int[]{-1, 2, 9}, 2) == 2 ? 1 : 0);
    }
}