題目

標題和出處

標題：連續的子數組和

出處：523. 連續的子數組和

難度

5 級

題目描述

要求

給定一個整數數組 $\text{nums}$ 和一個整數 $\text{k}$，如果 $\text{nums}$ 有一個連續子數組滿足大小至少為 $\text{2}$ 且元素和是 $\text{k}$ 的倍數，則返回 $\text{true}$，否則返回 $\text{false}$。

對于整數 $\text{x}$，如果存在一個整數 $\text{n}$ 使得 $\text{x}=\text{n}\times \text{k}$，則 $\text{x}$ 是 $\text{k}$ 的倍數。$\text{0}$ 總是 $\text{k}$ 的倍數。

示例

示例 1：

輸入：$\text{nums?=?[23,2,4,6,7],?k?=?6}$
輸出：$\text{true}$
解釋：$\text{[2,?4]}$ 是大小為 $\text{2}$ 的子數組，和為 $\text{6}$。

示例 2：

輸入：$\text{nums?=?[23,2,6,4,7],?k?=?6}$
輸出：$\text{true}$
解釋：$\text{[23,?2,?6,?4,?7]}$ 是大小為 $\text{5}$ 的子數組，和為 $\text{42}$。
$\text{42}$ 是 $\text{6}$ 的倍數，因為 $\text{42}=\text{7}\times \text{6}$ 且 $\text{7}$ 是一個整數。

示例 3：

輸入：$\text{nums?=?[23,2,6,4,7],?k?=?13}$
輸出：$\text{false}$

數據范圍

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{nums[i]}\le {\text{10}}^{\text{9}}$
• $\text{0}\le \text{sum(nums[i])}\le {\text{2}}^{\text{31}}?\text{1}$
• $\text{1}\le \text{k}\le {\text{2}}^{\text{31}}?\text{1}$

解法

思路和算法

只有當數組 $\text{nums}$ 的長度至少為 $2$ 時，才可能存在長度至少為 $2$ 的子數組。如果數組 $\text{nums}$ 的長度小于 $2$，則一定不存在長度至少為 $2$ 的子數組，返回 $\text{false}$。

當數組 $\text{nums}$ 的長度至少為 $2$ 時，為了計算數組 $\text{nums}$ 的子數組的元素和，需要計算數組 $\text{nums}$ 的前綴和，根據前綴和得到任意一個子數組的元素和。

為了判斷子數組的元素和是否為 $k$ 的倍數，需要計算前綴和模 $k$ 的余數。對于兩個不同的下標 $i$ 和 $j$，其中 $i<j$，如果這兩個下標對應的前綴和模 $k$ 的余數相同，則下標范圍 $[i+1,j]$ 的子數組的元素和為 $k$ 的倍數，該子數組的長度為 $j?i$。由于這道題要求子數組的長度至少為 $2$，因此應該尋找符合要求的最長子數組，需要記錄每個余數的第一次出現的下標。

從左到右遍歷數組 $\text{nums}$，遍歷過程中計算前綴和模 $k$ 的余數，并使用哈希表記錄每個余數的首次出現下標。由于空前綴不包含任何元素，前綴和為 $0$，余數也為 $0$，其下標為 $?1$，因此首先將余數 $0$ 對應下標 $?1$ 存入哈希表。

用 $\text{sum}$ 表示前綴和模 $k$ 的余數，初始時 $\text{sum}=0$。遍歷到每個元素時，將該元素值加到 $\text{sum}$，然后將 $\text{sum}$ 的值更新為 $\text{sum}\mathrm{mod}k$（應確保 $0\le \text{sum}<k$）。更新 $\text{sum}$ 的值之后，判斷哈希表中是否存在余數 $\text{sum}$，執行相應的操作。

• 如果哈希表中存在余數 $\text{sum}$，則從哈希表中得到 $\text{sum}$ 第一次出現的下標 $\text{prevIndex}$，用 $i$ 表示當前下標，則以當前元素結尾的和為 $k$ 的倍數的最長子數組的長度是 $i?\text{prevIndex}$，如果 $i?\text{prevIndex}\ge 2$，則找到一個長度至少為 $2$ 且和為 $k$ 的倍數的的子數組，返回 $\text{true}$。

• 如果哈希表中不存在余數 $\text{sum}$，則當前下標是余數 $\text{sum}$ 第一次出現，將 $\text{sum}$ 對應下標 $i$ 存入哈希表。

遍歷結束之后，如果沒有找到長度至少為 $2$ 且和為 $k$ 的倍數的的子數組，則返回 $\text{false}$。

由于哈希表中存儲的是每個余數第一次出現的下標，因此當遍歷到下標 $i$ 時，如果哈希表中存在相同余數的下標 $\text{prevIndex}$，則以下標 $i$ 結尾的和為 $k$ 的倍數的最長子數組的長度是 $i?\text{prevIndex}$。如果 $i?\text{prevIndex}<2$，則以下標 $i$ 結尾的子數組中不存在長度至少為 $2$ 且和為 $k$ 的倍數的子數組。因此上述做法可以確保得到正確的結果。

代碼

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int length = nums.length;if (length < 2) {return false;}Map<Integer, Integer> indices = new HashMap<Integer, Integer>();indices.put(0, -1);int sum = 0;for (int i = 0; i < length; i++) {sum = (sum + nums[i]) % k;if (indices.containsKey(sum)) {int prevIndex = indices.get(sum);if (i - prevIndex >= 2) {return true;}} else {indices.put(sum, i);}}return false;}
}

復雜度分析

• 時間復雜度：$O(n)$，其中 $n$ 是數組 $\text{nums}$ 的長度。需要遍歷數組一次計算前綴和模 $k$ 的余數，對于每個元素，更新余數、計算答案與操作哈希表的時間都是 $O(1)$。

• 空間復雜度：$O(k)$，其中 $k$ 是給定的整數。空間復雜度主要取決于哈希表，哈希表中的不同余數個數不超過 $k$ 個。