Re: [閒聊] 每日leetcode已回收
https://leetcode.com/problems/binary-subarrays-with-sum/
930. Binary Subarrays With Sum
給你一個包含0和1的陣列nums和一個數字goal，找出所有相加為goal的子陣列數量。
思路：
1.假設nums[i:j]是一個總和為 goal 的子陣列，如果 nums[i:j] + nums[j + 1] 也等於
goal 就會產生一個新的子陣列，我們可以用 map 統計前面出現過的和共有幾個然後
不斷累加。
2.要快速求得當前位置 j 到任意位置 i 的和數量可以使用前綴和搭配map統計，
如果i~j存在和相加等於 goal:
nums[0:j] - nums[0:i] = goal， nums[0:i] = nums[0:j] - goal
所以檢查 nums[0:j] - goal 這個key就可以。
pycode:
---------------------------------------------------
class Solution:
def numSubarraysWithSum(self, nums: List[int], goal: int) -> int:
map = {0: 1}
res = 0
num_sum = 0
for num in nums:
num_sum += num
if num_sum - goal in map:
res += map[num_sum - goal]
map[num_sum] = map.get(num_sum, 0) + 1
return res
---------------------------------------------------
--
https://i.imgur.com/hhXzZJ3.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.139.70.48 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710385960.A.307.html
推
03/14 11:18,
1年前
, 1F
03/14 11:18, 1F
推
03/14 11:22,
1年前
, 2F
03/14 11:22, 2F
→
03/14 11:22,
1年前
, 3F
03/14 11:22, 3F
→
03/14 12:07,
1年前
, 4F
03/14 12:07, 4F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 44 之 1548 篇)：