[Swift Weekly Contest 108]LeetCode930. 和相同的二元子数组 |

发布时间：2020-12-14 05:10:42 所属栏目：百科来源：网络整理

导读：In an array? A ?of? 0 s and? 1 s,how many?non-empty?subarrays have sum? S ? ?Example 1: Input: A = [1,1,1],S = 2 Output: 4 Explanation: The 4 subarrays are bolded below: [1,1] [1,1] ?Note: A.length = 30000 0 = S = A.length A[i] ?is either?

In an array?A?of?0s and?1s,how many?non-empty?subarrays have sum?S?

?Example 1:

Input: A = [1,1,1],S = 2 Output: 4 Explanation: The 4 subarrays are bolded below: [1,1] [1,1]

?Note:

A.length <= 30000
0 <= S <= A.length
A[i]?is either?0?or?1.

在由若干?0?和?1? 组成的数组?A?中，有多少个和为?S?的非空子数组。

?示例：

输入：A = [1,S = 2
输出：4
解释：
如下面黑体所示，有 4 个满足题目要求的子数组：
[1,1]
[1,1]

?提示：

A.length <= 30000
0 <= S <= A.length
A[i]?为?0?或?1

220ms

 1 class Solution {
 2     func numSubarraysWithSum(_ A: [Int],_ S: Int) -> Int {
 3         var n:Int = A.count
 4         var cum:[Int] = [Int](repeating: 0,count: n + 1)
 5         for i in 0..<n
 6         {
 7             cum[i + 1] = cum[i] + A[i]
 8         }
 9         
10         var ret:Int = 0
11         var f:[Int] = [Int](repeating: 0,count: 30003)
12         for i in 0...n
13         {
14             if cum[i] - S >= 0
15             {
16                 ret += f[cum[i] - S]
17             }
18             f[cum[i]] += 1
19         }
20         return ret
21     }
22 }

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!