Subarray Sum Equals K*
class Solution:
def subarraySum(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
"""
背後原理:
假設我們有 csumKey1 = cumulativeSum [i]為 nums[0] +...+ nums[i]的總和
且我們現在有 csumKey2 = cumulativeSum[j]: nums[0] + ... + nums[i] + ... nums[j]
若 csumKey2 - k = csumKey1 則我們可以宣稱找到一連續數和為 K
註:
若array中的元素皆為"非負整數" 則我們可以說 nums[i+1]~ nums[j] 的累加值為 k
若有負數則此法會無法知道 index 確切位置
Example: [3, 4, 7, 2, -3, 8] k = 7
index: 1 2 3 4 5 6
cSum: 3 7 14 16 11 19
^
這裡我們意識預先給 csumKey = 0 的值: {0:1} 然後宣稱找到第一個累加值為7
當 index = 3 時 我們把累加值減去 k : 14 - 7 = 7 然後去找是否有先前累加值為7的cSumkey
我們找到先前 cSumKey = 7 (index = 2) 此時我們可以宣稱找到一連續subarray累加值為 7
"""
my_dict = {0:1}
csum = 0
res = 0
for num in nums:
csum += num
res += my_dict.get(csum-k, 0)
my_dict[csum] = my_dict.get(csum, 0) + 1
return res
Last updated