LeetCode 560 和 K 的子陣列

給定乙個整數陣列和乙個整數 k，您需要找到該陣列中總和為 k 的連續子陣列的數量。

示例 1：

輸入：nums = [1,1,1]， k = 2

輸出：2、1,1] 和 [1,1] 是兩種不同的情況。

注意：陣列的長度為 [1， 20,000]。

陣列中元素的範圍是 [-1000， 1000]，整數 k 的範圍是 [-1e7， 1e7]。

雜湊表字首和阿里騰訊位元組的直觀方法是暴力破解所有子陣列，然後分別計算總和，如果等於 k，則計數為 +1這種做法的時間複雜度為 o（n 2），* 如下所示：

class solution: def subarraysum(self, nums: list[int], k: int) -int: cnt, n = 0, len(nums) for i in range(n): sum = 0 for j in range(i, n): sum += nums[j] if (sum == k): cnt += 1 return cnt

class solution: def subarraysum(self, nums: list[int], k: int) -int: cnt, n = 0, len(nums) pre = [0] *n + 1) for i in range(1, n + 1): pre[i] = pre[i - 1] +nums[i - 1] for i in range(1, n + 1): for j in range(i, n + 1): if (pre[j] -pre[i - 1] == k): cnt += 1 return cnt

這種方法的核心點是，找到的子陣列總數實際上等於：

以索引 0 結尾的子陣列數以索引 1 結尾的子陣列數... 以索引 n - 1 結尾的子陣列數和以索引 i 結尾的子陣列數等於：字首為 sum 的子陣列數為 acc - k，其中 acc 是當前字首的總和。 為了能夠快速提取字首和 acc - k 的數量，我們可以將其儲存在雜湊中。

具體演算法：維護乙個算力圖，算力圖的鍵是累積值 acc，該值是累積值 acc 的出現次數。 遍歷陣列，然後不斷更新 acc 和哈希圖，如果 acc 等於 k，那麼很明顯 +1如果hashmap[acc - k]存在，我們可以將其新增到結果中。 語言很難解釋，所以我畫了乙個圖表來說明 nums = [1,2,3,3,0,3,4,2]， k = 6 的情況。

如圖所示，當訪問 nums[3] 時，hashmap 如圖所示，計數為 2其中之一是[1,2,3]，這很容易理解。 另乙個是[3,3]。

這個 [3,3] 正是我們用 hashmap[acc - k] 得到的，即 hashmap[9 - 6]。

字首，並可用於通過利用雜湊對映記錄的總和來避免重複計數語言支援： js， pythonj**ascript code：

/* *lc app=leetcode id=560 lang=j**ascript * 560] subarray sum equals k *//** param nums * param k * return */var subarraysum = function (nums, k) ;let acc = 0; let count = 0; for (let i = 0; i < nums.length; i++)if (hashmap[acc] === void 0) else }return count;};

class solution: def subarraysum(self, nums: list[int], k: int) -int: d = {}acc = count = 0 for num in nums: acc += num if acc == k: count += 1 if acc - k in d: count += d[acc-k] if acc in d: d[acc] += 1 else: d[acc] = 1 return count