🔗 🟡 523. Continuous Subarray Sum

tags: `前綴和(Prefix Sum)` `雜湊表(Hash Table)` `同餘定理`

題意

給定一個整數陣列 $nums$ 和一個整數 $k$ ，檢查 $nums$ 中是否存在滿足以下條件的連續子陣列：

其長度至少為 $2$ ，且
該子陣列的元素和是 $k$ 的倍數。

如果存在，則返回 $\text{true}$ ；否則，返回 $\text{false}$ 。

約束條件

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

思路：前綴和(Prefix Sum) + 雜湊表(Hash Table) + 同餘定理

首先，我們可以使用前綴和(Prefix Sum) 來計算陣列中每個位置的前綴和，對於子陣列 $[l, r]$ 的和可以表示為 $s[r] - s[l-1]$ ，若其為 $k$ 的倍數，則 $s[r] \equiv s[l-1] \pmod{k}$ 。

故可以記錄每個前綴和對 $k$ 取模後的結果，由於子陣列的長度至少為 $2$ ，因此我們可以使用雜湊表來記錄每個前綴和對 $k$ 取模後的值及其對應的索引。若有兩個前綴和對 $k$ 取模後的結果相同，且其索引之差 $> 1$ ，則表示存在滿足條件的子陣列。

複雜度分析

時間複雜度： $\mathcal{O}(n)$ ，其中 $n$ 為陣列的長度。
空間複雜度： $\mathcal{O}(min(n, k))$ ，雜湊表的空間複雜度。

寫法一：一邊計算前綴和一邊檢查

一邊計算前綴和，一邊檢查是否存在滿足條件的子陣列，由於需要檢查距離是否大於 $1$ ，因此需要儲存每個前綴和對 $k$ 取模後的值第一次出現的索引。如果再次出現相同的前綴和，且其索引之差大於 $1$ ，則表示存在滿足條件的子陣列。

具體步驟如下：

初始化前綴和 $s$ 為 0，並建立一個雜湊表 $pos$ 用來存儲每個前綴和對 $k$ 取模後的值及其對應的索引。
我們預先在 $pos$ 中存儲一個初始值 $pos[0] = -1$ ，表示空的子陣列。
遍歷陣列 $nums$ ，對每個元素 $x$ 計算當前的前綴和 $s$ ，並對 $k$ 取模。
如果當前的前綴和 $s$ 已經存在於 $pos$ 中，檢查當前索引 $i$ 與 $pos[s]$ 之間的距離是否大於 $1$ 。如果大於 $1$ ，則表示存在滿足條件的子陣列，返回 $\text{true}$ 。
如果當前的前綴和 $s$ 不存在於 $pos$ 中，則將其加入 $pos$ 中，使得 $pos[s]$ 表示該前綴和第一次出現的索引。
遍歷結束後，如果沒有找到滿足條件的子陣列，返回 $\text{false}$ 。

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        s = 0
        pos = defaultdict(int) # key: sum % k, value: first index
        pos[0] = -1 # empty array
        for i, x in enumerate(nums):
            s = (s + x) % k
            if s in pos:
                if i - pos[s] > 1:
                    return True
            else:
                pos[s] = i
        return False

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        int s = 0;
        unordered_map<int, int> pos;
        pos[0] = -1;
        for (int i = 0; i < n; i++) {
            s = (s + nums[i]) % k;
            if (pos.count(s)) {
                if (i - pos[s] > 1) {
                    return true;
                }
            } else {
                pos[s] = i;
            }
        }
        return false;
    }
};

寫法二：事先計算前綴和，不用判斷距離

若事先計算前綴和，對於每次枚舉的位置 $i$ ，都把與當前位置距離大於 $1$ 的前綴和對 $k$ 取模後的值加入雜湊表中，則可以減少對於距離的判斷，並改為Hash Set來儲存。

具體步驟如下：

計算長度為 $n+1$ 的前綴和陣列 $s$ ，其中 $s[i] = \displaystyle\sum_{j=0}^{i-1} \text{nums}[j]$ = $s[i-1] + \text{nums}[i-1]$ 。
初始化一個空的集合 $pos$ 用來存儲前綴和對 $k$ 取模後的值。
遍歷前綴和陣列 $s$ ，對於每個位置 $i$ ，將 $s[i-2]$ 對 $k$ 取模後的值加入 $pos$ 中。
如果 $s[i]$ 對 $k$ 取模後的值在 $pos$ 中，則表示存在滿足條件的子陣列，返回 $\text{true}$ 。
遍歷結束後，如果沒有找到滿足條件的子陣列，返回 $\text{false}$ 。

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        n = len(nums)
        s = list(accumulate(nums, initial=0))
        pos = set()
        for i in range(2, n+1):
            pos.add(s[i-2] % k)
            if s[i] % k in pos:
                return True
        return False

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> s(n + 1, 0); // prefix sum
        for (int i = 1; i <= n; i++) s[i] = (s[i - 1] + nums[i - 1]) % k;
        unordered_set<int> pos;
        for (int i = 2; i <= n; i++) {
            pos.insert(s[i - 2]);
            if (pos.count(s[i])) return true;
        }
        return false;
    }
};