数组

大家好，我是老马。

今天我们一起来学习一下数组这种数据结构。

主要知识

数组需要拆分下面几个部分：

理论介绍
源码分析
数据结构实现？
题目练习（按照算法思想分类）
梳理对应的 sdk 包
应用实战

因为这个是 leetcode 系列，所以重点是 4、5(对4再一次总结)。

为了照顾没有基础的小伙伴，会简单介绍一下1的基础理论。

简单介绍1，重点为4。其他不是本系列的重点。

Sliding Window 滑动窗口

滑动窗口（Sliding Window）是一种常用于数组、字符串等线性数据结构中的算法技巧，特别适用于解决子区间或子串相关的问题，比如「最长子串」、「最大和子数组」、「包含某种元素的最小子数组」等。

🧠 核心思想

滑动窗口的本质就是两个指针形成一个窗口，然后在这个窗口内进行操作：

左指针表示窗口的起始位置
右指针表示窗口的结束位置（通常是开放的，即不包括右边界）

通过不断移动左右指针，动态维护这个窗口的状态，从而达到：

减少不必要的重复计算
降低时间复杂度

📦 常见类型

1. 固定长度窗口

适用于要求窗口长度固定的问题。

例题：求一个数组中所有长度为 k 的子数组的最大和。

public int maxSum(int[] nums, int k) {
    int sum = 0;
    for (int i = 0; i < k; i++) sum += nums[i];
    int max = sum;

    for (int i = k; i < nums.length; i++) {
        sum += nums[i] - nums[i - k];
        max = Math.max(max, sum);
    }

    return max;
}

2. 动态长度窗口（也叫可变窗口）

适用于窗口长度不确定，但要满足某种条件（比如：包含所有字符、和不超过某个值等）。

例题：最小覆盖子串（LeetCode 76）

public String minWindow(String s, String t) {
    int[] need = new int[128];
    for (char c : t.toCharArray()) need[c]++;
    
    int left = 0, right = 0, start = 0, minLen = Integer.MAX_VALUE, count = t.length();

    while (right < s.length()) {
        if (need[s.charAt(right++)]-- > 0) count--;

        while (count == 0) {
            if (right - left < minLen) {
                minLen = right - left;
                start = left;
            }

            if (++need[s.charAt(left++)] > 0) count++;
        }
    }

    return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}

🧩 适用场景

滑动窗口特别适合这些题型：

题型	举例
固定长度的子数组	最大/最小和、平均值
动态长度子数组	最小长度满足条件的区间
子串问题	最长无重复字符子串、最小覆盖子串
数量统计类	至多/至少包含 K 个不同字符的子串

⏱️ 时间复杂度分析

滑动窗口的优点之一就是：

每个元素最多进出窗口一次 ⇒ 整体复杂度为 O(n)，比暴力解法的 O(n²) 更高效。

🛠️ 实战技巧

窗口中需要统计什么内容？
- 比如：元素个数、元素频率、和等
什么时候扩展窗口（移动右指针）？
- 一般是为了让窗口「满足条件」
什么时候收缩窗口（移动左指针）？
- 一般是为了让窗口「不再满足条件」后恢复到合法状态
如何判断窗口是否满足条件？
- 常用的变量如：valid，count，match 等

滑动窗口看起来和双指针有些类似，二者的区别与联系

滑动窗口（Sliding Window）和双指针（Two Pointers）确实非常相似，很多人初学时容易混淆。

但它们其实是一对“重叠又有区别”的技巧，可以说：

滑动窗口是双指针的一种特化。

🧭 二者的联系

类别	滑动窗口 & 双指针
✅ 本质	都是用两个指针遍历数组（或字符串）
✅ 目的	减少暴力遍历的冗余计算，提升效率
✅ 复杂度	通常是 O(n)，而非 O(n²)
✅ 使用结构	线性结构：数组、字符串、链表等

🔍 核心区别对比

对比项	滑动窗口	双指针
📌 关注点	窗口内的内容（通常是连续子数组/子串）	两个位置的关系（可以连续，也可以不连续）
📐 应用场景	统计窗口内的信息（子数组和、字符频率、是否满足条件）	排序数组中的搜索、配对、快慢指针类问题
📊 窗口长度	通常变化的（动态窗口）、有时固定	不强调窗口，强调两个点
↔️ 移动方式	一般是 `right` 先动，再根据条件 `left` 动	两个指针可以一起动，也可以独立移动
💡 常配合结构	频率表、哈希表、前缀和等	不一定，有时只是比较值、移动位置

🧠 总结口诀

滑动窗口：用来统计连续区间的状态（子串、子数组等）
双指针：用来比较两个位置的值或找某种“配对”关系

✅ 简单区分建议：

你要做的事	用
子数组/子串统计、满足某种限制、最大最小长度等	滑动窗口
两端收缩查找、元素比较、链表操作等	双指针

🧪 如果你还在纠结，可以记住这三点：

滑动窗口一般处理连续的一段区间
双指针处理两个独立位置的值/关系
滑动窗口可以看作是“受控的”双指针

给出滑动窗口的经典题目，一简单，2中等，1困难

难度	题目编号 & 名称	链接	类型
简单	643. 子数组最大平均数 I	力扣链接	固定长度滑窗
中等	3. 无重复字符的最长子串	力扣链接	动态窗口 + 去重
中等	438. 找到字符串中所有字母异位词	力扣链接	动态窗口 + 频率统计
困难	76. 最小覆盖子串	力扣链接	动态窗口 + 最小长度

数组基本知识+技巧

分类	代表技巧
遍历类	遍历、双指针、滑窗
前缀/差分类	前缀和、差分、后缀数组
查找类	二分、哈希、离散化
空间/状态优化	状压、滚动数组、差分压缩
排序/归并类	排序、归并逆序对、树状数组、线段树
子数组/序列	动规、中心扩展、单调栈
矩阵类	二维差分、DFS/BFS、旋转模拟
特殊技巧	快速幂、滚动哈希、模拟题技巧

🎯 常见遍历技巧 + 力扣题目对照表

技巧	力扣题目	说明
基础遍历	27.移除元素	直接遍历+判断
快慢指针	26. 删除重复项	原地去重
左右夹逼	167.两数之和 II	排序+夹逼
滑动窗口	209. 长度最小子数组	动态控制窗口
子数组枚举	560. 和为K的子数组	前缀和优化
子序列枚举	491. 递增子序列	回溯
倒序遍历	198. 打家劫舍	动态规划
规则模拟	54. 螺旋矩阵	控制方向循环遍历

数组
- 主要知识
Sliding Window 滑动窗口
滑动窗口看起来和双指针有些类似，二者的区别与联系
给出滑动窗口的经典题目，一简单，2中等，1困难
数组基本知识+技巧
- 🎯 常见遍历技巧 + 力扣题目对照表

leetcode 数组专题之数组遍历-03-遍历 Sliding Window 滑动窗口介绍

数组