连续子串和的整除问题 - MarsCode

作过类似的啊lc560合为k的子数组——前缀和+哈希表-CSDN博客，咋还是没有第一时间想到哎。

方法：前缀和+哈希表

任意连续子数组subArr[i..j] = preSum[j] - preSum[i-1] 前缀和之差。那么subArr%b == 0即等价于

(preSum[j] - preSum[i-1]) % b == 0，等价于 preSum[j] % b  ==  preSum[i-1] % b。

那么在遍历求前缀和时，就一边更新前缀和，一边哈希记录已有的前缀和%b的数量，一边ans+=数量。

注意初始化map 有0,1键值对。

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    public static int solution(int n, int b, List<Integer> sequence) {
        // Please write your code here
        // 17.11
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1);

        int preSum = 0;
        int ans = 0;
        for(int num: sequence) {
            preSum = (preSum + num)%b;
            int existCount = map.getOrDefault(preSum, 0);
            ans += existCount;
            map.put(preSum, existCount+1);
        }
        // System.out.println(ans);
        return ans;
    }

    public static void main(String[] args) {
        // You can add more test cases here
        List<Integer> sequence = new ArrayList<>();
        sequence.add(1);
        sequence.add(2);
        sequence.add(3);
        System.out.println(solution(3, 3, sequence) == 3);
    }
}