Re: [閒聊] 每日leetcode已回收
※ 引述《Rushia (みけねこ的鼻屎)》之銘言：
: https://leetcode.com/problems/binary-subarrays-with-sum/
: 930. Binary Subarrays With Sum
: 給你一個包含0和1的陣列nums和一個數字goal，找出所有相加為goal的子陣列數量。
思路 :
(1)
sum為到i為止所有元素的總和，當sum==goal，ans++
用hash table，紀錄之前出現過的值，去找sum-goal之前出現過幾次，並加到ans
(2) sliding windows
設計一個function，可以找出一個array裡所有總和小於特定值的subarray
接著去找小於goal的subarray個數以及小於goal-1的subarray個數
兩個相減就是總和為goal的subarray的個數
golang code :
func numSubarraysWithSum(nums []int, goal int) int {
return count(nums,goal)-count(nums,goal-1)
}
func count(nums []int,goal int)int{
sum:=0
ans:=0
l:=0
for r:=0;r<len(nums);r++{
sum+=nums[r]
for r>=l && sum>goal{
sum-=nums[l]
l++
}
ans+=r-l+1
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.69.200 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1710413228.A.DCB.html
→
03/14 18:57,
1年前
, 1F
03/14 18:57, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 45 之 1548 篇)：