6个高效算法问题（避免 O(n^2) 解法）

### 6 个高效算法问题（避免 $O(n^2)$  解法）

针对给定的无序整数数组 $S$（长度 $n$，$ 1 \leq n \leq 100K$），解决以下 6 个高效算法问题（避免 $O(n^2)$ 解法）。

#### 1. 判断是否存在重复元素对

**目标**：检测数组中是否有至少一对重复整数。

**算法**：使用 **哈希集合（HashSet）**。

- 遍历数组，将每个元素插入哈希集合。
- 若插入时发现元素已存在，返回 `true`。
- 遍历结束未发现重复，返回 `false`。

**时间复杂度**：$O(n)$（哈希集合插入/查找平均 $O(1)$）。

**空间复杂度**：$O(n)$（最坏情况存储所有元素）。

#### 2. 寻找和为 $v$ 的两个整数

**目标**：给定整数 $v$，找到 $a, b \in S$ 使得 $a + b = v$。

**算法**：使用 **哈希表（HashMap）**。

- 遍历数组，对每个元素 $x$：
  - 计算补数 $y = v - x$。
  - 若 $y$ 在哈希表中，返回 $(x, y)$。
  - 否则，将 $x$ 存入哈希表。
- 遍历结束未找到，返回 `无解`。

**时间复杂度**：$O(n)$（单次遍历 + 哈希查找）。

**空间复杂度**：$O(n)$（哈希表存储元素）。

#### 3. 有序数组的和为 $v$ 的两个整数

**目标**：数组 $S$ 已排序，寻找 $a + b = v$。

**算法**：使用 **双指针（Two Pointers）**。

- 初始化左指针 $l = 0$，右指针 $r = n-1$。
- 循环直到 $l \geq r$：
  - 若 $S[l] + S[r] = v$，返回 $(S[l], S[r])$。
  - 若和小于 $v$，$l$ 右移（增大和）。
  - 若和大于 $v$，$r$ 左移（减小和）。

**时间复杂度**：$O(n)$（双指针遍历一次）。

**空间复杂度**：$O(1)$（仅需两个指针）。

#### 4. 打印区间 $[a, b]$ 内的整数（有序输出）

**目标**：输出数组中所有满足 $a \leq x \leq b$ 的整数，按升序排列。

**算法**：

1. 对数组排序（$O(n \log n)$）。
2. 遍历排序后的数组，输出区间内的元素。

**时间复杂度**：$O(n \log n)$（排序主导）。

**空间复杂度**：$O(1)$（若原地排序，否则 $O(n)$）。

#### 5. 最长连续递增子数组的长度

**目标**：找到最长的连续子数组（元素递增且连续）。

**算法**：使用 **动态规划（DP）** 或 **一次遍历**。

- 初始化当前长度 $cur = 1$，最大长度 $max = 1$。
- 从第 2 个元素遍历到末尾：
  - 若 $S[i] > S[i-1]$，$cur++$；否则 $cur = 1$。
  - 更新 $max = \max(max, cur)$。

**时间复杂度**：$O(n)$（单次遍历）。

**空间复杂度**：$O(1)$（仅需常数变量）。

#### 6. 求数组的中位数（$n$ 为奇数）

**目标**：找到数组的中位数（第 $ 50$ 百分位数）。

**算法**：

1. 对数组排序（$O(n \log n)$）。
2. 返回中间元素 $S[n/2]$。

**时间复杂度**：$O(n \log n)$（排序主导）。

**空间复杂度**：$O(1)$（若原地排序，否则 $O(n)$）。

### 总结

| 问题 | 算法 | 时间复杂度 | 空间复杂度 |
| :--- | :--- | :--- | :--- |
| 重复元素检测 | 哈希集合 | $O(n)$ | $O(n)$ |
| 和为 $v$ 的两数（无序） | 哈希表 | $O(n)$ | $O(n)$ |
| 和为 $v$ 的两数（有序） | 双指针 | $O(n)$ | $O(1)$ |
| 区间内整数输出 | 排序 + 遍历 | $O(n \log n)$ | $O(1)$ |
| 最长连续递增子数组 | 一次遍历 | $O(n)$ | $O(1)$ |
| 中位数（$n$ 为奇数） | 排序 | $O(n \log n)$ | $O(1)$ |

以上算法均满足 $n \leq 100K$ 的效率要求，避免了 $O(n^2)$ 的暴力解法。