题目链接

523. 连续的子数组和

思路

参考宫水三叶大佬题解

一开始以为和 Leetcode 53 Maximum Subarray 思路差不多，都是求子数组的值。但是后来发现在53题中并没有求出每个子数组的和，只是在贪心的情况下求出了可能的最大和

代码

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        int[] sum = new int[n + 1];
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i - 1] + nums[i - 1];
        }

        Set<Integer> set = new HashSet<>();
        for(int i = 2; i <= n; i++){
            set.add(sum[i - 2] % k);
            if(set.contains(sum[i] % k)){
                return true;
            }
        }

        return false;
    }
}