套路

前缀和

滑动窗口

分为不定长（最小，最大），定长窗口

时间复杂度都是ON

排列，组合，子集背诵

排列：

组合：

子集：

时间复杂度

“区分 O(n) 和 O(n²) 主要看指针是否会反复从头开始。像冒泡排序那样，每次外层循环都让内层从 0 跑到 n，就是 O(n²)。但滑动窗口里，l 和 r 都是单调递增的，每个字符只会进窗口和出窗口一次，总次数是线性的，所以是 O(n)。”

🚩 常见时间复杂度 & 如何看出来

1. O(1) 常数时间

• 特征：执行步骤跟输入规模无关。
• 例子：

int x = arr[5];   // 随机访问数组
map.put("a", 1);  // HashMap 插入

• 技巧：只要操作次数固定，不随 n 增长，就是 O(1)。

---

2. O(log n) 对数时间

• 特征：每次操作把问题规模缩小一半。
• 例子：

// 二分查找
while (low <= high) {
    mid = (low + high) / 2;
    ...
}

• 技巧：遇到 “二分 / 分治” → log n。

---

3. O(n) 线性时间

• 特征：每个元素只处理有限次（常数次）。
• 例子：

for (int i = 0; i < n; i++) {
    ...
}

或滑动窗口：左右指针各走一遍数组。

• 技巧：数一数元素最多被访问几次，如果 ≤ 常数次 → O(n)。

---

4. O(n log n)

• 特征：线性扫描 + 对数拆分。
• 典型：排序算法（快排、归并、堆排）。
  • 快排：O(n) 分区 + O(log n) 递归深度 → O(n log n)。
  • 堆排序：每次调整堆 O(log n)，n 次 → O(n log n)。
• 技巧：看到 “排序”、“分治+合并”，大概率是 O(n log n)。

---

5. O(n²)

• 特征：双重循环，内层循环和外层循环完全独立。
• 例子：

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        ...
    }
}

• 技巧：如果每次外层循环都让内层跑一遍 n → O(n²)。

---

6. O(2^n) 指数级

• 特征：每一步有两个分支，递归深度为 n。
• 例子：子集枚举、回溯搜索。

void dfs(int i) {
    if (i == n) return;
    dfs(i+1);   // 选
    dfs(i+1);   // 不选
}

→ 共 2^n 种可能。

• 技巧：遇到 “子集 / 全排列 / 括号生成” → 可能是指数复杂度。

---

7. O(n!) 阶乘级

• 特征：枚举全排列。
• 例子：旅行商问题，生成 n 个数的全排列。
• 技巧：看到 “全排列” → n!。