LCP 68. 美观的花束

题目链接：https://leetcode.cn/problems/1GxJYY/

代码

/**
 * LCP 68. 美观的花束
 * https://leetcode.cn/problems/1GxJYY/
 */

function beautifulBouquet(flowers: number[], cnt: number): number {
    let left = 0;
    let res = 0;
    const map = new Map<number, number>();
    for (let i = 0; i < flowers.length; i++) {
        map.set(flowers[i], (map.get(flowers[i]) || 0) + 1);
        while (map.get(flowers[i])! > cnt) {
            const fl = map.get(flowers[left])!;
            if (fl === 1) {
                map.delete(flowers[left]);
            }
            else {
                map.set(flowers[left], fl - 1);
            }
            left++;
        }
        res += i - left + 1;
    }
    return res;
}

思路

滑动窗口 + 哈希表统计每种花的数量：

1. 使用哈希表 map 记录窗口内每种花的数量

2. 对于每个右端点 i：

   • 将 flowers[i] 加入窗口，更新计数
   • 当某种花的数量超过 cnt 时，收缩左边界 left，直到该花的数量不超过 cnt
   • 以 i 为右端点的所有有效子数组数量为 i - left + 1

3. 累加所有右端点对应的子数组数量

• 时间复杂度 $O(n)$，每个元素最多被访问两次（加入和移除窗口各一次）
• 空间复杂度 $O(n)$，哈希表最多存储 $n$ 种不同的花