LeetCode 930: binary subarrays with sum

发表于 | | 阅读次数:
字数统计: 281 | 阅读时长 ≈ 1

题目链接

https://leetcode.com/problems/binary-subarrays-with-sum/

题意

给一个仅包含0和1的数组A(A.length <= 30000)，求非空的和为S(0 <= S <= A.length)的子数组序列个数。

题目类型

智力

题目分析

不算很难的题目，写出来主要是因为最开始用的是滑动窗口过于麻烦，后面才发现部分和两下就解决了，警醒一下。

解的时候遍历数组A同时求一下部分和cur += A[i]，以当前位置为子区间右端点的满足部分和为S的数目就是部分和为cur - S的端点的数目和，用个f数组存一下数目就好了。

注意一下因为这样得到的区间数目左侧是开区间，所以开头要来个f[0] = 1。

时间复杂度

$O(N)$

源代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int numSubarraysWithSum(vector<int>& A, int S) {
        int n = A.size();
        int f[30020];
        int cur = 0, ans = 0;
        memset(f, 0, sizeof(f));
        f[0] = 1;
        for(int i = 0; i < n; i++) {
            cur += A[i];
            if (cur - S >= 0)
                ans += f[cur - S];
            f[cur] += 1;
        }
        return ans;
    }
};
0%