LeetCode 523. 连续的子数组和

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 取模哈希（推荐）
相似题目

题目描述

✅ 523. 连续的子数组和

思路分析

解法一：前缀和 + 取模哈希（推荐）

核心思路：

设前缀和 pre[i]，若 (pre[j] - pre[i]) % k == 0，则 pre[i] % k == pre[j] % k。

用哈希表记录某个余数最早出现的位置，保证子数组长度至少为 2。

k == 0 时只需判断是否存在连续两个 0。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(min(n, k))，其中 k 表示取模基数。

import java.util.*;

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        if (k == 0) {
            for (int i = 1; i < nums.length; i++) {
                if (nums[i] == 0 && nums[i - 1] == 0) {
                    return true;
                }
            }
            return false;
        }

        Map<Integer, Integer> first = new HashMap<>();
        first.put(0, -1);
        int sum = 0;

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int mod = sum % k;
            if (mod < 0) {
                mod += k;
            }

            if (first.containsKey(mod)) {
                if (i - first.get(mod) >= 2) {
                    return true;
                }
            } else {
                first.put(mod, i);
            }
        }

        return false;
    }
}

func checkSubarraySum(nums []int, k int) bool {
	if k == 0 {
		for i := 1; i < len(nums); i++ {
			if nums[i] == 0 && nums[i-1] == 0 {
				return true
			}
		}
		return false
	}

	first := map[int]int{0: -1}
	sum := 0

	for i, v := range nums {
		sum += v
		mod := sum % k
		if mod < 0 {
			mod += k
		}

		if idx, ok := first[mod]; ok {
			if i-idx >= 2 {
				return true
			}
		} else {
			first[mod] = i
		}
	}

	return false
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和、哈希表
974. 和可被 K 整除的子数组	中等	前缀和、同余
525. 连续数组	中等	前缀和、哈希表
930. 和相同的二元子数组	中等	前缀和、滑动窗口
1248. 统计「优美子数组」	中等	前缀和、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/66697457