LeetCode: 523. Continuous Subarray Sum

友情支持

如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜

支付宝

有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。

wx jikerizhi

公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。

523. Continuous Subarray Sum

Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.

Example 1:

Input: [23, 2, 4, 6, 7],  k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.

Example 2:

Input: [23, 2, 6, 4, 7],  k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.

Note:

The length of the array won’t exceed 10,000.
You may assume the sum of all the numbers is in the range of a signed 32-bit integer.

解题分析

利用同余定理：

当 \(prefixSums[q]−prefixSums[p]\) 为 \(k\) 的倍数时，\(prefixSums[p]\) 和 \(prefixSums[q]\) 除以 \(k\) 的余数相同。（D瓜哥注：余数相同，则相减之后余数就被减掉了。）因此只需要计算每个下标对应的前缀和除以 \(k\) 的余数即可，使用哈希表存储每个余数第一次出现的下标。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * 参考 https://leetcode.cn/problems/continuous-subarray-sum/solutions/807930/lian-xu-de-zi-shu-zu-he-by-leetcode-solu-rdzi/[523. 连续的子数组和 - 官方题解^]
 *
 * @author D瓜哥 · https://www.diguage.com
 * @since 2024-06-23 00:23:40
 */
public boolean checkSubarraySum(int[] nums, int k) {
  if (nums == null || nums.length < 2) {
    return false;
  }
  Map<Integer, Integer> remainderToIndexMap = new HashMap<>();
  // 当 sum=0 时，还没有任何数字参与，所以是 -1
  remainderToIndexMap.put(0, -1);
  int remainder = 0;
  for (int i = 0; i < nums.length; i++) {
    // 同余定理
    remainder = (remainder + nums[i]) % k;
    if (remainderToIndexMap.containsKey(remainder)) {
      int prevIndex = remainderToIndexMap.get(remainder);
      if (i - prevIndex >= 2) {
        return true;
      }
    } else {
      // 前面已经判断过是否包含该值，
      // 这里也就不需要为了保存最小的下标去判断是否已经存在该值
      remainderToIndexMap.put(remainder, i);
    }
  }
  return false;
}