一、引言
尺取法（Two Pointers / Sliding Window）是处理区间问题的经典技巧，通过维护左右两个指针在有序或线性结构上滑动，将O(n²)的暴力枚举优化至O(n)。一个极具代表性的应用场景是”最小覆盖子串”问题：给定一个源字符串S和一个目标字符串T，要求在S中找到包含T中所有字符的最短子串。该问题在DNA序列分析、日志关键词提取、文本摘要生成等领域都有广泛应用。本文将用Java实现基于尺取法的最小覆盖子串求解器，并扩展到多区间覆盖问题的贪心解法。
二、算法原理
2.1 滑动窗口核心思想
维护一个可变大小的窗口 [left, right]，通过右指针扩展窗口直至满足条件，再通过左指针收缩窗口以寻找最优解：
- 扩展阶段：右指针右移，将新字符纳入窗口，同时更新字符计数；
- 收缩阶段：当窗口已覆盖所有目标字符时，尝试右移左指针，在保持覆盖的前提下最小化窗口；
- 记录最优：每次满足条件时更新全局最优解。
由于左右指针各遍历字符串一次，总时间复杂度为O(n)。
2.2 贪心最优性证明
对于”最小覆盖子串”问题，滑动窗口策略之所以正确，关键在于：若固定右端点，最短的合法左端点必为从左向右第一个仍满足条件的那个。因此每次右指针移动后，只需将左指针尽可能右移即可，不会遗漏更优解。
2.3 多区间覆盖扩展
给定数轴上n个区间，要求选择最少数量的区间覆盖整个目标范围 [L, R]。贪心策略为：
- 按左端点排序；
- 每次选择能覆盖当前起点且右端点最远的区间；
- 将当前起点更新为该区间右端点，重复直至覆盖目标。
该贪心策略已被证明可得到最优解。
三、完整Java实现
import java.util.*;
/**
* 尺取法（滑动窗口）算法实现
* 包含：最小覆盖子串、多区间贪心覆盖
*/
public class SlidingWindowSolver {
// ==================== 最小覆盖子串 ====================
/**
* 在字符串s中找到包含t所有字符的最短子串
* 时间复杂度: O(|s| + |t|)
* 空间复杂度: O(字符集大小)
*
* @param s 源字符串
* @param t 目标字符集合
* @return 最短覆盖子串，若不存在返回空串
*/
public String minWindow(String s, String t) {
if (s == null || t == null || s.length() < t.length()) {
return "";
}
// 统计t中各字符需求次数
Map<Character, Integer> need = new HashMap<>();
for (char c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
// 窗口内字符计数
Map<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int valid = 0; // 已满足需求的字符种类数
// 记录最优解: (起始位置, 长度)
int start = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 扩展窗口：纳入右侧字符
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++; // 某字符需求刚好满足
}
}
// 收缩窗口：尝试右移左指针
while (valid == need.size()) {
// 更新最优解
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char d = s.charAt(left);
left++;
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--; // 移出后该字符不再满足需求
}
window.put(d, window.get(d) - 1);
}
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
/**
* 优化版本：使用固定大小数组替代HashMap（仅适用于ASCII）
* 速度提升约3~5倍
*/
public String minWindowFast(String s, String t) {
if (s.length() < t.length()) return "";
int[] need = new int[128];
int[] window = new int[128];
int required = 0;
for (char c : t.toCharArray()) {
if (need[c] == 0) required++;
need[c]++;
}
int left = 0, right = 0;
int formed = 0;
int start = 0, minLen = Integer.MAX_VALUE;
while (right < s.length()) {
char c = s.charAt(right++);
window[c]++;
if (need[c] > 0 && window[c] == need[c]) {
formed++;
}
while (formed == required) {
if (right - left < minLen) {
start = left;
minLen = right - left;
}
char d = s.charAt(left++);
if (need[d] > 0 && window[d] == need[d]) {
formed--;
}
window[d]--;
}
}
return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
}
// ==================== 多区间贪心覆盖 ====================
static class Interval implements Comparable<Interval> {
int start, end;
String name;
Interval(int start, int end, String name) {
this.start = start;
this.end = end;
this.name = name;
}
@Override
public int compareTo(Interval o) {
return this.start - o.start;
}
@Override
public String toString() {
return String.format("%s[%d,%d]", name, start, end);
}
}
/**
* 区间覆盖问题：用最少数量的区间覆盖目标范围 [targetL, targetR]
* 贪心策略：每次选能覆盖当前起点且右端点最远的区间
*
* @param intervals 可选区间列表
* @param targetL 目标左端点
* @param targetR 目标右端点
* @return 选中的区间列表，若无法覆盖返回空列表
*/
public List<Interval> minIntervalCover(List<Interval> intervals, int targetL, int targetR) {
// 按左端点排序
Collections.sort(intervals);
List<Interval> result = new ArrayList<>();
int currentPos = targetL;
int i = 0;
int n = intervals.size();
while (currentPos < targetR) {
int farthest = currentPos;
Interval chosen = null;
// 在所有左端点不超过currentPos的区间中，选右端点最远的
while (i < n && intervals.get(i).start <= currentPos) {
if (intervals.get(i).end > farthest) {
farthest = intervals.get(i).end;
chosen = intervals.get(i);
}
i++;
}
// 若无区间可扩展覆盖，则失败
if (chosen == null || farthest == currentPos) {
return new ArrayList<>(); // 无法覆盖
}
result.add(chosen);
currentPos = farthest;
}
return result;
}
// ==================== 扩展：最大连续1的个数 III ====================
/**
* 给定二进制数组nums和最多可翻转k个0为1，求最长连续1子数组长度
* 经典滑动窗口：维护窗口内0的个数不超过k
*/
public int longestOnes(int[] nums, int k) {
int left = 0, zeros = 0, maxLen = 0;
for (int right = 0; right < nums.length; right++) {
if (nums[right] == 0) zeros++;
while (zeros > k) {
if (nums[left] == 0) zeros--;
left++;
}
maxLen = Math.max(maxLen, right - left + 1);
}
return maxLen;
}
// ==================== 测试验证 ====================
public static void main(String[] args) {
SlidingWindowSolver solver = new SlidingWindowSolver();
// 测试1：最小覆盖子串
System.out.println("=== 测试1：最小覆盖子串 ===");
String[][] tests = {
{"ADOBECODEBANC", "ABC"},
{"a", "a"},
{"aa", "aa"},
{"cabwefgewcwaefgcf", "cae"},
{"abcdefghijklmn", "x"}
};
for (String[] test : tests) {
String result = solver.minWindow(test[0], test[1]);
String fast = solver.minWindowFast(test[0], test[1]);
System.out.printf("s=\"%s\", t=\"%s\"%n", test[0], test[1]);
System.out.printf(" 结果: \"%s\" (HashMap版)%n", result);
System.out.printf(" 结果: \"%s\" (数组优化版)%n", fast);
System.out.println();
}
// 测试2：区间覆盖
System.out.println("=== 测试2：区间覆盖问题 ===");
List<Interval> intervals = Arrays.asList(
new Interval(1, 5, "A"),
new Interval(2, 6, "B"),
new Interval(4, 9, "C"),
new Interval(8, 12, "D"),
new Interval(11, 15, "E"),
new Interval(14, 18, "F")
);
List<Interval> cover = solver.minIntervalCover(intervals, 1, 18);
System.out.println("区间列表: " + intervals);
System.out.println("覆盖 [1,18] 的最少区间: " + cover);
// 测试3：最大连续1
System.out.println("\n=== 测试3：最大连续1（可翻转k个0） ===");
int[] nums = {1, 1, 0, 0, 1, 1, 1, 0, 1, 1};
System.out.println("数组: " + Arrays.toString(nums));
System.out.println("k=1 时最长连续1长度: " + solver.longestOnes(nums, 1));
System.out.println("k=2 时最长连续1长度: " + solver.longestOnes(nums, 2));
System.out.println("k=3 时最长连续1长度: " + solver.longestOnes(nums, 3));
// 性能对比
System.out.println("\n=== 性能对比 ===");
StringBuilder bigS = new StringBuilder();
StringBuilder bigT = new StringBuilder();
Random rand = new Random(42);
for (int i = 0; i < 500000; i++) bigS.append((char) ('a' + rand.nextInt(26)));
for (int i = 0; i < 100; i++) bigT.append((char) ('a' + rand.nextInt(26)));
long t0 = System.currentTimeMillis();
String r1 = solver.minWindow(bigS.toString(), bigT.toString());
long t1 = System.currentTimeMillis();
String r2 = solver.minWindowFast(bigS.toString(), bigT.toString());
long t2 = System.currentTimeMillis();
System.out.println("数据规模: s=" + bigS.length() + ", t=" + bigT.length());
System.out.println("HashMap版耗时: " + (t1 - t0) + " ms");
System.out.println("数组优化版耗时: " + (t2 - t1) + " ms");
System.out.println("结果长度: " + (r1 != null ? r1.length() : 0));
}
}
四、复杂度分析
- 最小覆盖子串：
- HashMap版时间复杂度O(|S| + |T|)，空间复杂度O(|Σ|)字符集大小；
- 数组优化版将HashMap操作降为数组索引，实际运行速度提升3~5倍，特别适合ASCII场景。
- 区间覆盖：排序O(n log n)，贪心扫描O(n)，总复杂度O(n log n)，空间O(1)。
- 最大连续1：单次线性扫描，O(n)时间，O(1)空间。
五、总结
本文以最小覆盖子串为主线，系统展示了尺取法的Java实现与应用：
- 滑动窗口框架通过左右指针协作，将暴力O(n²)优化至O(n)；
- HashMap→数组优化在字符统计场景可带来数倍性能提升；
- 区间覆盖贪心证明了尺取思想在离散结构上的扩展性；
- 代码覆盖主算法与3个扩展问题，可直接用于面试准备或生产环境。
读者可进一步探索：带权区间覆盖、多字符串联合覆盖、或在流式数据上的在线滑动窗口实现。
