做移动网站排名软件,汽修厂营销活动方案,南山网站设计,0基础学做网站教程文章目录1. 题目2. 解题1. 题目
在由若干 0 和 1 组成的数组 A 中#xff0c;有多少个和为 S 的非空子数组。
示例#xff1a;
输入#xff1a;A [1,0,1,0,1], S 2
输出#xff1a;4
解释#xff1a;
如下面黑体所示#xff0c;有 4 个满足题目要求的子数组#xff…
文章目录1. 题目2. 解题1. 题目
在由若干 0 和 1 组成的数组 A 中有多少个和为 S 的非空子数组。
示例
输入A [1,0,1,0,1], S 2
输出4
解释
如下面黑体所示有 4 个满足题目要求的子数组
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]
[1,0,1,0,1]提示
A.length 30000
0 S A.length
A[i] 为 0 或 1来源力扣LeetCode 链接https://leetcode-cn.com/problems/binary-subarrays-with-sum 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
类似题目 LeetCode 523. 连续的子数组和求余 哈希 LeetCode 525. 连续数组前缀和哈希 LeetCode 560. 和为K的子数组前缀和差分 LeetCode 974. 和可被 K 整除的子数组哈希map LeetCode 1248. 统计「优美子数组」要复习
class Solution {
public:int numSubarraysWithSum(vectorint A, int S) {int n A.size(), sum 0, i 0, count 0;unordered_mapint,int m;//sum, 有多少个m[0] 1;//等于0的有1个for(i 0; i n; i) {sum A[i];//前缀和if(m.find(sum-S) ! m.end())count m[sum-S];//前缀和减去S后的前缀和存在中间段就是和为S的m[sum];}return count;}
};124 ms 30.5 MB 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
