如何优化大数组滑动窗口子数组转Set的嵌套循环？

当然可以优化！你的原始解法在N达到1e6的时候肯定会超时——毕竟O(N*K)的时间复杂度，当K也比较大时，运算量直接爆炸。我们可以用滑动窗口+计数哈希表的思路，把时间复杂度降到O(N)，彻底去掉嵌套循环。

核心思路 #

相邻的两个长度为K的连续子数组，其实只有首尾两个元素不同：前一个窗口的第一个元素会被移出，后一个窗口的最后一个新元素会被加入。我们不需要每次都重新遍历整个窗口，只需要基于前一个窗口的统计结果，做增量更新即可：

• 先用哈希表统计第一个窗口内每个元素的出现次数，同时记录当前窗口的唯一元素数量（哈希表中键的总数）。
• 从第二个窗口开始，滑动窗口时：
  1. 移除窗口左侧的元素：如果该元素的计数减到0，说明它在当前窗口中已不存在，唯一元素数量减1；否则仅减少计数。
  2. 添加窗口右侧的新元素：如果该元素之前的计数是0，说明它是当前窗口的新唯一元素，唯一元素数量加1；然后增加计数。
  3. 每次滑动后，更新全局的最大唯一元素数量。

优化后的Java代码 #

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

public class Main {
    public static void main(String[] args) {
        int[] Ar = {1,2,3,4,5};
        int N = Ar.length;
        int K = 3;
        
        if (K == 0 || N == 0) {
            System.out.println(0);
            return;
        }
        
        Map<Integer, Integer> countMap = new HashMap<>();
        int currentUnique = 0;
        int maxUnique = 0;
        
        // 初始化第一个窗口
        for (int i = 0; i < K; i++) {
            int num = Ar[i];
            int count = countMap.getOrDefault(num, 0);
            if (count == 0) {
                currentUnique++;
            }
            countMap.put(num, count + 1);
        }
        maxUnique = currentUnique;
        
        // 滑动窗口处理剩余部分
        for (int i = K; i < N; i++) {
            // 移除左边的元素（i-K位置的元素）
            int leftNum = Ar[i - K];
            int leftCount = countMap.get(leftNum);
            if (leftCount == 1) {
                currentUnique--;
            }
            countMap.put(leftNum, leftCount - 1);
            
            // 添加右边的新元素
            int rightNum = Ar[i];
            int rightCount = countMap.getOrDefault(rightNum, 0);
            if (rightCount == 0) {
                currentUnique++;
            }
            countMap.put(rightNum, rightCount + 1);
            
            // 更新最大值
            if (currentUnique > maxUnique) {
                maxUnique = currentUnique;
            }
        }
        
        System.out.println(maxUnique);
    }
}

为什么这个方法更高效？ #

• 时间复杂度是O(N)：每个元素只会被加入哈希表一次、移除一次，哈希表的get和put操作平均时间复杂度是O(1)，整体没有嵌套循环。
• 空间复杂度是O(min(K, M))，其中M是数组中不同元素的总数，最坏情况下是O(K)，但对于1e6的N来说完全可控。

内容的提问来源于stack exchange，提问作者Subham