leetcode 523. Continuous Subarray Sum | 523. 连续的子数组和（同余定理）

本文主要是介绍leetcode 523. Continuous Subarray Sum | 523. 连续的子数组和（同余定理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目

https://leetcode.com/problems/continuous-subarray-sum/

题解

没有想到 O(n) 的方法，于是直奔答案：

参考1：【宫水三叶】拓展到求方案数问题
参考2：证明+动图：帮你吃透本题

核心思想：

草稿：

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int[] sum = new int[nums.length];sum[0] = nums[0];for (int i = 1; i < nums.length; i++) {sum[i] = sum[i - 1] + nums[i];}HashMap<Integer, Integer> map = new HashMap<>(); // (从0开始的前缀和%k，对应的结束下标)map.put(0, -1); // e.g. nums=[2,4,7]for (int i = 0; i < nums.length; i++) {if (map.containsKey(sum[i] % k)) {if (i - map.get(sum[i] % k) >= 2) return true;} else {map.put(sum[i] % k, i);}}return false;}
}

这篇关于leetcode 523. Continuous Subarray Sum | 523. 连续的子数组和（同余定理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---