[Swift]LeetCode1248.统计「优美子数组」|CountNumberofNiceSubarrays

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（let_us_code）
➤博主域名：https://www.zengqiang.org
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array of integers nums and an integer k. A subarray is called nice if there are k odd numbers on it.

Return the number of nice sub-arrays.

Example 1:

Input: nums = [1,1,2,1,1], k = 3
Output: 2
Explanation: The only sub-arrays with 3 odd numbers are [1,1,2,1] and [1,2,1,1].
Example 2:

Input: nums = [2,4,6], k = 1
Output: 0
Explanation: There is no odd numbers in the array.
Example 3:

Input: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
Output: 16

Constraints:

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

给你一个整数数组 nums 和一个整数 k。

如果某个连续子数组中恰好有 k 个奇数数字，我们就认为这个子数组是「优美子数组」。

请返回这个数组中「优美子数组」的数目。

示例 1：

输入：nums = [1,1,2,1,1], k = 3
输出：2
解释：包含 3 个奇数的子数组是 [1,1,2,1] 和 [1,2,1,1] 。
示例 2：

输入：nums = [2,4,6], k = 1
输出：0
解释：数列中不包含任何奇数，所以不存在优美子数组。
示例 3：

输入：nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出：16

提示：

1 <= nums.length <= 50000
1 <= nums[i] <= 10^5
1 <= k <= nums.length

1056ms

 1 class Solution {
 2     func numberOfSubarrays(_ nums: [Int], _ k: Int) -> Int {
 3         var oddIndex = [Int]()
 4         var res = 0
 5         var p = 0
 6         for i in 0 ..< nums.count where nums[i] % 2 != 0 {
 7             if oddIndex.count >= k {
 8                 res += (oddIndex[p] - (p > 0 ? oddIndex[p - 1] : -1)) * (i - oddIndex.last!)
 9                 p += 1
10             }
11             oddIndex.append(i)
12         }
13         
14         if oddIndex.count >= k {
15             res += (oddIndex[p] - (p > 0 ? oddIndex[p - 1] : -1)) * (nums.count - oddIndex.last!)   
16         }
17         
18         return res
19     }
20 }

1068ms

 1 class Solution {
 2     func numberOfSubarrays(_ nums: [Int], _ k: Int) -> Int {
 3         return atMostK(nums, k) - atMostK(nums, k - 1)
 4     }
 5     
 6     private func atMostK(_ nums: [Int], _ count: Int) -> Int {
 7         var count = count
 8         var res = 0
 9         var i = 0
10         for j in 0..<nums.count {
11             if nums[j] % 2 == 1 {
12                 count -= 1
13             }
14             
15             while count < 0 {
16                 if nums[i] % 2 == 1 {
17                     count += 1
18                 }
19                 i += 1
20             }
21             res += j - i + 1
22         }
23         return res
24     }
25 }

1076ms

 1 class Solution {
 2     func numberOfSubarrays(_ nums: [Int], _ k: Int) -> Int {
 3         if nums.count == 0 {
 4             return 0
 5         }
 6         var oddPosition : [Int] = []
 7         for i in 0...nums.count - 1 {
 8             if nums[i] % 2 == 1 {
 9                 oddPosition.append(i)
10             }
11         }
12         if oddPosition.count < k {
13             return 0
14         }
15         oddPosition.insert(-1,at:0)
16         oddPosition.append(nums.count)
17         
18         var result = 0
19         for  i in 1...oddPosition.count - k - 1 {
20             result += (oddPosition[i] - oddPosition[i-1])*(oddPosition[i+k] - oddPosition[i+k-1])
21         }
22         return result
23     }
24 }