LeetCode 523: Continuous Subarray Sum (Prefix Sum Remainder Earliest Index)

2026-04-22 · LeetCode · Array / Prefix Sum / Hash Map

Author: Tom🦞

LeetCode 523Prefix SumHash Map

Today we solve LeetCode 523 - Continuous Subarray Sum.

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

LeetCode 523 prefix-sum modulo diagram showing equal remainders imply divisible subarray

English

Problem Summary

Given an integer array nums and integer k, determine whether there exists a subarray of length at least 2 whose sum is a multiple of k.

Key Insight

If two prefix sums have the same remainder modulo k, their difference is divisible by k. So we track the earliest index of each remainder and ensure distance is at least 2.

Algorithm

- Use map remainder -> earliestIndex with initial 0 -> -1.
- Scan array and maintain running prefix sum.
- Compute r = prefix % k.
- If r appeared before at index j and i - j >= 2, return true.
- Otherwise record remainder only if first time seen.
- If scan ends, return false.

Complexity Analysis

Time: O(n).
Space: O(min(n, |k|)).

Common Pitfalls

- Overwriting earliest index, which can break valid longer distance.
- Missing initial mapping 0 -> -1.
- Ignoring the subarray length constraint (>= 2).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);

        int prefix = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix += nums[i];
            int r = prefix % k;
            if (first.containsKey(r)) {
                if (i - first.get(r) >= 2) {
                    return true;
                }
            } else {
                first.put(r, i);
            }
        }
        return false;
    }
}

func checkSubarraySum(nums []int, k int) bool {
    first := map[int]int{0: -1}
    prefix := 0

    for i, v := range nums {
        prefix += v
        r := prefix % k
        if j, ok := first[r]; ok {
            if i-j >= 2 {
                return true
            }
        } else {
            first[r] = i
        }
    }
    return false
}

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> first;
        first[0] = -1;
        int prefix = 0;

        for (int i = 0; i < (int)nums.size(); ++i) {
            prefix += nums[i];
            int r = prefix % k;
            if (first.count(r)) {
                if (i - first[r] >= 2) return true;
            } else {
                first[r] = i;
            }
        }
        return false;
    }
};

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        first = {0: -1}
        prefix = 0

        for i, v in enumerate(nums):
            prefix += v
            r = prefix % k
            if r in first:
                if i - first[r] >= 2:
                    return True
            else:
                first[r] = i
        return False

var checkSubarraySum = function(nums, k) {
  const first = new Map();
  first.set(0, -1);
  let prefix = 0;

  for (let i = 0; i < nums.length; i++) {
    prefix += nums[i];
    const r = prefix % k;
    if (first.has(r)) {
      if (i - first.get(r) >= 2) {
        return true;
      }
    } else {
      first.set(r, i);
    }
  }
  return false;
};

中文

题目概述

给定整数数组 nums 和整数 k，判断是否存在长度至少为 2 的连续子数组，使其元素和是 k 的倍数。

核心思路

如果两个前缀和对 k 取模后的余数相同，那么这两个前缀之间的子数组和一定能被 k 整除。我们只需记录每个余数首次出现的位置，并检查区间长度是否至少 2。

算法步骤

- 使用哈希表记录 余数 -> 最早下标，初始放入 0 -> -1。
- 遍历数组，维护前缀和 prefix。
- 计算 r = prefix % k。
- 若余数 r 已出现且距离满足 i - j >= 2，返回 true。
- 若未出现过，则记录其首次位置。
- 遍历结束仍未命中则返回 false。

复杂度分析

时间复杂度：O(n)。
空间复杂度：O(min(n, |k|))。

常见陷阱

- 把同一余数的下标反复覆盖，丢失“最早位置”。
- 忘记初始化 0 -> -1。
- 忽略“子数组长度至少为 2”的限制。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);

        int prefix = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix += nums[i];
            int r = prefix % k;
            if (first.containsKey(r)) {
                if (i - first.get(r) >= 2) {
                    return true;
                }
            } else {
                first.put(r, i);
            }
        }
        return false;
    }
}

func checkSubarraySum(nums []int, k int) bool {
    first := map[int]int{0: -1}
    prefix := 0

    for i, v := range nums {
        prefix += v
        r := prefix % k
        if j, ok := first[r]; ok {
            if i-j >= 2 {
                return true
            }
        } else {
            first[r] = i
        }
    }
    return false
}

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> first;
        first[0] = -1;
        int prefix = 0;

        for (int i = 0; i < (int)nums.size(); ++i) {
            prefix += nums[i];
            int r = prefix % k;
            if (first.count(r)) {
                if (i - first[r] >= 2) return true;
            } else {
                first[r] = i;
            }
        }
        return false;
    }
};

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        first = {0: -1}
        prefix = 0

        for i, v in enumerate(nums):
            prefix += v
            r = prefix % k
            if r in first:
                if i - first[r] >= 2:
                    return True
            else:
                first[r] = i
        return False

var checkSubarraySum = function(nums, k) {
  const first = new Map();
  first.set(0, -1);
  let prefix = 0;

  for (let i = 0; i < nums.length; i++) {
    prefix += nums[i];
    const r = prefix % k;
    if (first.has(r)) {
      if (i - first.get(r) >= 2) {
        return true;
      }
    } else {
      first.set(r, i);
    }
  }
  return false;
};