Marscode连续子串和的整除问题——前缀和+哈希表

连续子串和的整除问题 - 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.11Map<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 hereList<Integer> sequence = new ArrayList<>();sequence.add(1);sequence.add(2);sequence.add(3);System.out.println(solution(3, 3, sequence) == 3);}
}