主題

LeetCode - 560. Subarray Sum Equals K 解題心得

Not In My Back Yard | 2021-05-05 00:00:03 | 巴幣 0 | 人氣 17

題目連結:


題目意譯:
給定一整數陣列 nums 以及一整數 k,回傳元素總和恰好為 k 的連續子陣列之個數。

限制:
1 ≦ nums.length ≦ 2 * 10 ^ 4
-1000 ≦ nums[i] ≦ 1000
-10 ^ 7 ≦ k ≦ 10 ^ 7



範例測資:
範例 1:
輸入: nums = [1,1,1], k = 2
輸出: 2

範例 2:
輸入: nums = [1,2,3], k = 3
輸出: 2


解題思維:
將 nums 按照前綴和(Prefix Sum)的精神求得
P[0] = 0 、
P[1] = nums[0]、
P[2] = P[1] + nums[1]、
P[3] = P[2] + nums[2]、
……以此類推。

而當有一數對 (i, j) 滿足 i < j 且 P[i] = P[j] - k(即 P[j] - P[i] = k)時,我們便找到了一個子陣列 nums[i] ~ nums[j - 1] 其總和為 k。

此時,我們可以利用雜湊表 H(Hash Table)將前綴和之值存入統計個數。當我們在計算 P[j] 時,我們已經將 P[0] ~ P[j - 1] 全數存入 H 中。

此時我們去 H 中尋找是否存在 P[i] 值滿足 P[i] = P[j] - k。如果存在則這樣子的 P[i] 之個數為 H[P[j] - k] 個。

將所有的 P[j] 計算其 H[P[j] - k] (如果存在)並加總即是所求。




此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。

創作回應

更多創作