class Solution {public int subarraySum(int[] nums, int k) {// 滑動窗口+前綴和int n = nums.length;int[] prevSum = new int[n + 1];for (int i = 1; i < n + 1; i++) {prevSum[i] = prevSum[i - 1] + nums[i - 1];}int ans = 0;Map<Integer, Integer> cnt = new HashMap<>(n + 1); // 設置容量可以快 2msfor (int prev : prevSum) {ans += cnt.getOrDefault(prev - k, 0);cnt.merge(prev, 1, Integer::sum); // cnt[sj]++}return ans;}
}

參考了大佬的寫法：

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;int[] prevSum = new int[n + 1];for (int i = 1; i <= n; i++) prevSum[i] = prevSum[i - 1] + nums[i - 1];Set<Integer> exist = new HashSet<>();for (int i = 2; i < n + 1; i++) {exist.add(prevSum[i - 2] % k);if (exist.contains(prevSum[i] % k)) {return true;}}return false;}
}

看了答案處理負數，直接加個k。

class Solution {public int subarraysDivByK(int[] nums, int k) {int n = nums.length;int[] prevSum = new int[n + 1];for (int i = 1; i < n + 1; i++) {prevSum[i] = prevSum[i - 1] + nums[i - 1];}int ans = 0;int[] map = new int[k];for (int prev: prevSum) {int key = (prev % k + k) % k;ans += map[key];map[key]++;}return ans;}
}