์ฐ์์ ์ผ๋ก ๋์ด๋ N๊ฐ์ ์๊ฐ ์์ ๋ ํน์ ๊ตฌ๊ฐ์ ๋ชจ๋ ์๋ฅผ ํฉํ ๊ฐ์ ๊ณ์ฐํ๋ ๋ฌธ์
Prefix Sum์ ๋ฐฐ์ด์ ๋งจ ์๋ถํฐ ํน์ ์์น๊น์ง์ ํฉ์ ๋ฏธ๋ฆฌ ๊ตฌํด ๋์ ๊ฒ์ ์๋ฏธํ๋ค.
์ด Prefix Sum์ ํ์ฉํ๋ฉด ๊ตฌ๊ฐ ํฉ์ ์ฝ๊ฒ ๊ณ์ฐํ ์ ์๋ค.
์๋ฅผ ๋ค์ด ๋ฐฐ์ด์ Left
๋ฒ์งธ ์์๋ถํฐ Right
๋ฒ์งธ ์์๊น์ง ๋ํ ๊ฐ์ Prefix Sum์ ๋ฐฐ์ด P
์ Right
๋ฒ์งธ ์์ ๊ฐ์์ Left - 1
์์ ๊ฐ์ ๋บ ๊ฐ์ด๋ค.
LeetCode 560๋ฒ ๋ฌธ์ ๋ ๋ฐฐ์ด์ ํน์ ๊ตฌ๊ฐ์ ํฉ์ด k๊ฐ ๋๋ ๊ฒฝ์ฐ์ ์๋ฅผ ๊ตฌํ๋ ๋ฌธ์ ์ด๋ค.
์ด ๋ฌธ์ ๋ prefix sum ๊ฐ๋ ๊ณผ dictionary๋ฅผ ํ์ฉํด์ ํ ์ ์๋ค.
class Solution(object):
def subarraySum(self, nums, k):
result = 0 # ๊ฐ๋ฅํ ๊ฒฝ์ฐ์ ์
prefix_sum = 0 # ๋์ ํฉ
d = {0: 1} # ๋์ ํฉ์ dictionary
for i in nums:
prefix_sum = prefix_sum + i
# (ํ์ฌ๊น์ง์ ๋์ ํฉ prefix_sum - ๋ชฉํ๊ฐ k)๊ฐ ๋์ ํฉ dictionary์ ์๋ค๋ฉด
# ๋ชฉํ๊ฐ k๋ฅผ ๋ง๋ค ์ ์๋ ๊ตฌ๊ฐ์ด ์กด์ฌํ๋ค๋ ๊ฒ
# ๊ฐ๋ฅํ ๊ฒฝ์ฐ์ ์์ d[prefix_sum - k]๋งํผ์ ์ถ๊ฐ
if prefix_sum - k in d:
result = result + d[prefix_sum - k]
# ๋์
๋๋ฆฌ์ ๊ฐ ์ฑ์ ๋ฃ๊ธฐ
if prefix_sum not in d:
d[prefix_sum] = 1
else:
d[prefix_sum] = d[prefix_sum] + 1
return result