Re: [闲聊] 每日leetcode

楼主: Rushia (みけねこ的鼻屎)   2024-03-14 11:12:36
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:
作者: JIWP (JIWP)   2024-03-14 11:18:00
大师,我看比较快的都是用sliding window
作者: DJYOSHITAKA (Evans)   2024-03-14 11:22:00
大湿
作者: oin1104 (是oin的说)   2024-03-14 11:22:00
大师
楼主: Rushia (みけねこ的鼻屎)   2024-03-14 12:07:00
双指针不太好想

Links booklink

Contact Us: admin [ a t ] ucptt.com