题目

image.png

思路

  • 思路一：暴力枚举，通过双重循环来计算不同起点i的前缀和（指为奇数的个数和），从而计算最终结果。

  • 思路二：前缀和+HashMap，由于暴力枚举要计算不同起点的前缀和，但是和可以使用HashMap来优化计算过程，pre[i] - pre[j] = k表示以i结尾的前缀和减去以j结尾的前缀和的值等于k，将问题转换为pre[i] - k = pre[j]，相当于求pre[j]的值，其中j < i，也就是求比i小的前缀和中有多少个值等于pre[i]-k，这是就可以使用map简化计算

    代码

    1.     //1.暴力枚举
    2.   public int numberOfSubarrays(int[] nums, int k) {
    3.       int res = 0;
    4.       for (int i = 0; i < nums.length; i++) {
    5.           int count = 0;
    6.           for (int j = i; j < nums.length; j++) {
    7.               count += nums[j] & 1;
    8.               if (count == k) res++;
    9.           }
    10.       }
    11.       return res;
    12.   }
    14.   //2.前缀和 + HashMap优化计算
    15.   public int numberOfSubarrays(int[] nums, int k) {
    16.       int res = 0, count = 0;
    17.       Map<Integer, Integer> map = new HashMap<>();
    18.       map.put(0, 1);
    19.       for (int num : nums) {
    20.           count += (num & 1);
    21.           res += map.getOrDefault(count - k, 0);
    22.           map.put(count, map.getOrDefault(count, 0) + 1);
    23.       }
    24.       return res;
    25.   }
    27.   //3.前缀和 + 数组优化计算
    28.   public int numberOfSubarrays(int[] nums, int k) {
    29.       int res = 0, count = 0;
    30.       int[] pre = new int[nums.length + 1];
    31.       pre[0] = 1;
    32.       for (int num : nums) {
    33.           count += (num & 1);
    34.           res += count >= k ? pre[count - k] : 0;
    35.           pre[count]++;
    36.       }
    37.       return res;
    38.   }

    统计[优美子数组]