一【題目類別】

• 前綴和

二【題目難度】

• 中等

三【題目編號】

• 523.連續(xù)的子數(shù)組和

四【題目描述】

• 給你一個整數(shù)數(shù)組 nums 和一個整數(shù) k ，如果 nums 有一個 好的子數(shù)組 返回 true ，否則返回 false：
• 一個 好的子數(shù)組 是：
  • 長度 至少為 2 ，且
  • 子數(shù)組元素總和為 k 的倍數(shù)。
• 注意：
  • 子數(shù)組 是數(shù)組中 連續(xù) 的部分。
  • 如果存在一個整數(shù) n ，令整數(shù) x 符合 x = n * k ，則稱 x 是 k 的一個倍數(shù)。0 始終 視為 k 的一個倍數(shù)。

五【題目示例】

• 示例 1：

  • 輸入：nums = [23,2,4,6,7], k = 6
  • 輸出：true
  • 解釋：[2,4] 是一個大小為 2 的子數(shù)組，并且和為 6 。

• 示例 2：

  • 輸入：nums = [23,2,6,4,7], k = 6
  • 輸出：true
  • 解釋：[23, 2, 6, 4, 7] 是大小為 5 的子數(shù)組，并且和為 42 。
    42 是 6 的倍數(shù)，因為 42 = 7 * 6 且 7 是一個整數(shù)。

• 示例 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$

七【解題思路】

• 前綴和思想：設(shè) prefix_sum[i] 表示數(shù)組 nums 的前綴和，即 prefix_sum[i] 表示 nums 從第 0 到第 i 的元素的和。對于任意兩個下標 i 和 j（i < j），子數(shù)組 nums[i+1:j+1] 的和可以表示為 prefix_sum[j] - prefix_sum[i]。
• 取模運算：我們需要找到兩個前綴和 prefix_sum[j] 和 prefix_sum[i]，使得它們的差 prefix_sum[j] - prefix_sum[i] 是 k 的倍數(shù)。我們可以通過對前綴和取模的方式（哈希表）來簡化這個問題：如果 prefix_sum[j] % k == prefix_sum[i] % k，那么 prefix_sum[j] - prefix_sum[i] 一定是 k 的倍數(shù)（同余定理）。
• 邊界情況處理：
  • 如果 k == 0，則子數(shù)組的和必須為 0，所以需要特判。
  • 由于子數(shù)組的長度至少為 2，所以當找到滿足條件的前綴和時，還需要確保兩個下標之間的距離大于等于 2。
• 最后返回結(jié)果即可
• 具體細節(jié)可以參考下面的代碼

八【時間頻度】

• 時間復(fù)雜度：$O(m)$，$m$為傳入的數(shù)組的長度
• 空間復(fù)雜度：$O(min(m,k))$，$m$為傳入的數(shù)組的長度，$k$為計算得到的余數(shù)的個數(shù)

九【代碼實現(xiàn)】

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;}// 檢查當前取模后的前綴和是否已經(jīng)在哈希表中if (hashMap.containsKey(prefixSum)) {// 如果存在，并且下標差大于等于 2，則找到符合條件的子數(shù)組if (i - hashMap.get(prefixSum) > 1) {return true;}} else {// 不存在則記錄當前前綴和對應(yīng)的下標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 = 0for i, num in enumerate(nums):# 更新前綴和prefix_sum += numif k != 0:# 對 k 取模prefix_sum %= k# 檢查當前取模后的前綴和是否已經(jīng)在哈希表中if prefix_sum in hash_map:# 如果存在，并且下標差大于等于 2，則找到符合條件的子數(shù)組if i - hash_map[prefix_sum] > 1:return Trueelse:# 不存在則記錄當前前綴和對應(yīng)的下標hash_map[prefix_sum] = ireturn 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;}// 檢查當前取模后的前綴和是否已經(jīng)在哈希表中if (hashMap.find(prefixSum) != hashMap.end()) {// 如果存在，并且下標差大于等于 2，則找到符合條件的子數(shù)組if (i - hashMap[prefixSum] > 1) {return true;}} else {// 不存在則記錄當前前綴和對應(yīng)的下標hashMap[prefixSum] = i;}}return false;}
};

十【提交結(jié)果】

1. Java語言版
   

2. Python語言版
   

3. C++語言版