523. Continuous Subarray Sum 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int[] preSumArray = new int[nums.length + 1];
        for (int i = 1; i < preSumArray.length; i++) {
            preSumArray[i] = preSumArray[i - 1] + nums[i - 1];
        }

        Set<Integer> reminderSet = new HashSet<>();
        for (int i = 2; i < preSumArray.length; i++) {
            reminderSet.add(preSumArray[i - 2] % k); // 注意此行非常关键，保证 reminderSet 为两个元素前数组前缀和的余数
            if (reminderSet.contains(preSumArray[i] % k)) {
                return true;
            }
        }

        return false;
    }
}

该题难点为转换题意，即转化出前缀和余数相等这一特性。

References

523. Continuous Subarray Sum