LeetCode 1248. 统计「优美子数组」

Categories:

题目描述
思路分析
1. 解法一：前缀计数（推荐）
相似题目

题目描述

✅ 1248. 统计「优美子数组」

思路分析

解法一：前缀计数（推荐）

核心思路：

将数组元素按奇偶映射为 0/1，统计前缀奇数个数。

用哈希表记录每个前缀奇数次数的出现频次。

对每个位置，累加 prefix - k 的出现次数。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于哈希表。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int numberOfSubarrays(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        count.put(0, 1);

        int odd = 0;
        int res = 0;

        for (int num : nums) {
            if ((num & 1) == 1) {
                odd++;
            }
            res += count.getOrDefault(odd - k, 0);
            count.put(odd, count.getOrDefault(odd, 0) + 1);
        }

        return res;
    }
}

func numberOfSubarrays(nums []int, k int) int {
	count := make(map[int]int)
	count[0] = 1

	odd := 0
	res := 0

	for _, num := range nums {
		if num&1 == 1 {
			odd++
		}
		res += count[odd-k]
		count[odd]++
	}

	return res
}

相似题目

题目	难度	考察点
1248. 统计「优美子数组」	中等	前缀和
930. 和相同的二元子数组	中等	前缀和
525. 连续数组	中等	前缀和
560. 和为 K 的子数组	中等	前缀和
1524. 和为奇数的子数组数目	中等	前缀和

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/64589289