LeetCode|1248.优美子数组--C++题解

//LeetCode1248题 统计【优美子数组】//给你一个整数数组 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//输出：1//提示：//1 <= nums.length <= 50000//1 <= nums[i] <= 10 ^ 5//1 <= k <= nums.length
//解题：//1.遍历一次数组计算所有的奇数获取下标位//2.根据输入的K值计算奇数下标外侧左右的长度//3.根据递推出的公式 x*y+x+y+1算出数组

#include<iostream>#include<vector>
using namespace std;
int numberOfSubarrays(vector<int>&, int);
int main(int argc, char** argv) {  vector<int> nums = { 2,2,2,1,2,2,1,2,2,2 };
  numberOfSubarrays(nums, 2);
  return 0;}
int numberOfSubarrays(vector<int>& nums, int k){  int subarrays = 0;  vector<int> tmp;  //计算出所有奇数存入新的数组中  for (int i = 0; i < nums.size(); ++i) {    if (nums[i] & 1) tmp.push_back(i);  }
  for (int j = 0; j < tmp.size(); ++j) {    //启始下标    int beginidx = tmp[j];    //结束下标    int endidx = (j + k - 1 >= tmp.size()) ? -1 : tmp[j + k - 1];
    //当结束下标不为-1时开始计算数组个数，否则为0    if (endidx != -1) {      //计算当前数组的前面偶数个数      int x = (j == 0) ? beginidx : beginidx - tmp[j - 1] - 1;      //计算当前数组后面的偶数个数      int y = (j + k >= tmp.size()) ? nums.size() - tmp[j + k - 1] - 1 : tmp[j + k] - tmp[j + k - 1] - 1;
      //累加当前个数      subarrays += x * y + x + y + 1;    }  }
  return 0;}