【LeetCode每日一题】——523.连续的子数组和

一【题目类别】

• 前缀和

二【题目难度】

• 中等

三【题目编号】

• 523.连续的子数组和

四【题目描述】

• 给你一个整数数组 nums 和一个整数 k ，如果 nums 有一个 好的子数组 返回 true ，否则返回 false：
• 一个 好的子数组 是：
  • 长度 至少为 2 ，且
  • 子数组元素总和为 k 的倍数。
• 注意：
  • 子数组 是数组中 连续 的部分。
  • 如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终 视为 k 的一个倍数。

五【题目示例】

• 示例 1：

  • 输入：nums = [23,2,4,6,7], k = 6
  • 输出：true
  • 解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

• 示例 2：

  • 输入：nums = [23,2,6,4,7], k = 6
  • 输出：true
  • 解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
    42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

• 示例 3：

  • 输入：nums = [23,2,6,4,7], k = 13
  • 输出：false

六【题目提示】

• $1<=nums.length<=10^5$
• $0<=nums[i]<=10^9$
• $0<=sum(nums[i])<=2^{31}-1$
• $1<=k<=2^{31}-1$

七【解题思路】

• 前缀和思想：设 prefix_sum[i] 表示数组 nums 的前缀和，即 prefix_sum[i] 表示 nums 从第 0 到第 i 的元素的和。对于任意两个下标 i 和 j（i < j），子数组 nums[i+1:j+1] 的和可以表示为 prefix_sum[j] - prefix_sum[i]。
• 取模运算：我们需要找到两个前缀和 prefix_sum[j] 和 prefix_sum[i]，使得它们的差 prefix_sum[j] - prefix_sum[i] 是 k 的倍数。我们可以通过对前缀和取模的方式（哈希表）来简化这个问题：如果 prefix_sum[j] % k == prefix_sum[i] % k，那么 prefix_sum[j] - prefix_sum[i] 一定是 k 的倍数（同余定理）。
• 边界情况处理：
  • 如果 k == 0，则子数组的和必须为 0，所以需要特判。
  • 由于子数组的长度至少为 2，所以当找到满足条件的前缀和时，还需要确保两个下标之间的距离大于等于 2。
• 最后返回结果即可
• 具体细节可以参考下面的代码

八【时间频度】

• 时间复杂度：$O(m)$，$m$为传入的数组的长度
• 空间复杂度：$O(min(m,k))$，$m$为传入的数组的长度，$k$为计算得到的余数的个数

九【代码实现】

1. Java语言版

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        // 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置
        HashMap<Integer, Integer> hashMap = new HashMap<Integer, Integer>();
        hashMap.put(0, -1);
        // 初始化前缀和
        int prefixSum = 0;
        for (int i = 0; i < nums.length; i++) {
            // 更新前缀和
            prefixSum += nums[i];
            if (k != 0) {
                // 对 k 取模
                prefixSum %= k;
            }
            // 检查当前取模后的前缀和是否已经在哈希表中
            if (hashMap.containsKey(prefixSum)) {
                // 如果存在，并且下标差大于等于 2，则找到符合条件的子数组
                if (i - hashMap.get(prefixSum) > 1) {
                    return true;
                }
            } else {
                // 不存在则记录当前前缀和对应的下标
                hashMap.put(prefixSum, i);
            }
        }
        return false;
    }
}

2. Python语言版

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
         # 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置
        hash_map = {0: -1}
        # 初始化前缀和
        prefix_sum = 0
        for i, num in enumerate(nums):
            # 更新前缀和
            prefix_sum += num
            if k != 0:
                # 对 k 取模
                prefix_sum %= k
            # 检查当前取模后的前缀和是否已经在哈希表中
            if prefix_sum in hash_map:
                # 如果存在，并且下标差大于等于 2，则找到符合条件的子数组
                if i - hash_map[prefix_sum] > 1:
                    return True
            else:
                # 不存在则记录当前前缀和对应的下标
                hash_map[prefix_sum] = i
        return False

3. C++语言版

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        // 用于存储取模后的前缀和与其下标, 初始化表示前缀和为0时在-1位置
        unordered_map<int, int> hashMap;
        hashMap[0] = -1;
        // 初始化前缀和
        int prefixSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            // 更新前缀和
            prefixSum += nums[i];
            if (k != 0) {
                // 对 k 取模
                prefixSum %= k;
            }
            // 检查当前取模后的前缀和是否已经在哈希表中
            if (hashMap.find(prefixSum) != hashMap.end()) {
                // 如果存在，并且下标差大于等于 2，则找到符合条件的子数组
                if (i - hashMap[prefixSum] > 1) {
                    return true;
                }
            } else {
                // 不存在则记录当前前缀和对应的下标
                hashMap[prefixSum] = i;
            }
        }
        return false;
    }
};

十【提交结果】

1. Java语言版
   

2. Python语言版
   

3. C++语言版