題目資訊

題目編號: 325
題目連結: Maximum Size Subarray Sum Equals k
主題: Array, Hash Table, Prefix Sum

題目敘述

給定一個整數數組 nums 和一個整數 k，返回其總和為 k 的最長子數組的長度。如果沒有，則返回0。

範例 1：

輸入： nums = [1,-1,5,-2,3], k = 3
輸出： 4
解釋：子數組 [1, -1, 5, -2] 的總和為 3，且是最長的子數組。

範例 2：

輸入： nums = [-2,-1,2,1], k = 1
輸出： 2
解釋：子數組 [-1, 2] 的總和為 1，且是最長的子數組。

限制條件：

$1 <= nums.length <= 2 \times 10^5$
$-10^4 <= nums[i] <= 10^4$
$-10^9 <= k <= 10^9$

直覺

這個問題要求找出一個子陣列，其總和等於給定的整數 $k$，並且該子陣列的長度為最大。直接的方法是探索所有可能的子陣列並計算其總和，但由於涉及到的大型陣列尺寸限制，這樣的做法在效率上不太理想。因此，我們可以利用前綴和(prefix sums)及雜湊表(hash maps)來快速識別符合條件的子陣列。

解法

解決方案使用了前綴和技術，結合雜湊表來有效判斷總和為 $k$ 的最長子陣列的長度。以下是逐步的過程：

初始化變數：
- length: 儲存輸入陣列 nums 的大小。
- maxLength: 初始化為 0，用來記錄找到的總和為 $k$ 的子陣列的最大長度。
- prefixSum: 初始化為 0，以保持目前經過的元素的累計和。
雜湊表設置：
- 使用一個雜湊表 prefixSumIndices 來記錄每個前綴和第一次出現的位址。這個映射將前綴和作為鍵，對應的索引作為值。
- 在雜湊表中插入初始項目 {0: -1}。這用作基礎情況來處理從開始位置就合計為 $k$ 的子陣列情形。
遍歷陣列：
- 遍歷陣列 nums 中的每個元素：
  - 透過加上當前的元素 nums[i] 來更新 prefixSum。
  - 檢查是否有一個前綴和滿足 prefixSum - k。如果存在，這意味著從找到的前綴和的下一個位置到當前索引 i 存在一個合計為 $k$ 的子陣列。
  - 使用 i - prefixSumIndices[prefixSum - k] 計算這個子陣列的長度，如果當前子陣列比先前找到的子陣列還長則更新 maxLength。
  - 如果目前的 prefixSum尚未被記錄，則在雜湊表 prefixSumIndices 中註冊其第一次出現。
返回結果：
- 處理完所有元素後，maxLength 的值將是總和為 $k$ 的最長子陣列的長度。返回此值作為結果。

通過這種方法，我們實現了時間複雜度為 $O(n)$，其中 $n$ 是陣列 nums 的長度，因此即使對於大的輸入規模也具有效率。使用雜湊表確保我們能夠快速尋找所需的前綴和差別，並透過僅維持每個前綴和的第一次出現來消除冗餘計算。

程式碼

C++

class Solution {
public:
    int maxSubArrayLen(vector<int>& nums, int k) {
        int length = nums.size();
        int maxLength = 0;
        long long prefixSum = 0;
        
        // 使用哈希表來儲存每個前綴和第一次出現的索引
        unordered_map<long long, int> prefixSumIndices;
        prefixSumIndices[0] = -1;  // 初始化將前綴和0設為索引-1
        
        for (int i = 0; i < length; i++) {
            prefixSum += nums[i];  // 更新累積的前綴和

            // 檢查是否存在子陣列的和等於k
            if (prefixSumIndices.find(prefixSum - k) != prefixSumIndices.end()) {
                // 如果此子陣列更長，則更新maxLength
                maxLength = max(maxLength, i - prefixSumIndices[prefixSum - k]);
            }
            
            // 記錄當前前綴和首次出現的索引
            if (prefixSumIndices.find(prefixSum) == prefixSumIndices.end()) {
                prefixSumIndices[prefixSum] = i;
            }
        }
        
        return maxLength;
    }
};

Python

class Solution:
    def maxSubArrayLen(self, nums, k):
        length = len(nums)
        maxLength = 0
        prefixSum = 0

        # 使用雜湊表來儲存每個前綴和的首次出現
        prefixSumIndices = {}
        prefixSumIndices[0] = -1  # 初始化前綴和0在索引-1

        for i in range(length):
            prefixSum += nums[i]  # 更新目前的前綴和

            # 檢查是否存在一個子陣列的和等於k
            if prefixSum - k in prefixSumIndices:
                # 如果這個子陣列更長，更新maxLength
                maxLength = max(maxLength, i - prefixSumIndices[prefixSum - k])

            # 記錄目前前綴和的首次出現
            if prefixSum not in prefixSumIndices:
                prefixSumIndices[prefixSum] = i

        return maxLength

複雜度分析

時間複雜度: $O(n)$
該演算法涉及對數組 nums 進行一次遍歷，此數組包含 $n$ 個元素。在每次遍歷中，操作如更新前綴和以及在哈希表中檢查/添加條目需要平均常數時間 $O(1)$。因此，總的時間複雜度為 $O(n)$。
空間複雜度: $O(n)$
使用了一個哈希表來存儲前綴和，其中每個前綴和都與其在數組中的索引相關聯。在最壞情況下，所有元素會產生唯一的前綴和，導致哈希表中存儲 $n$ 個條目。故空間複雜度為 $O(n)$。

CS Note
En

Leetcode 325. Maximum Size Subarray Sum Equals k

題目資訊

題目敘述

直覺

解法

程式碼

C++

Python

複雜度分析