数组与字符串操作 - 双指针技巧详解

一、问题引入

作为前端开发工程师,你一定遇到过这些场景:

场景1: 实时搜索优化

// 用户在搜索框输入,需要实时过滤列表
const users = ['Alice', 'Bob', 'Charlie', 'David'];
// 如何高效地找到包含特定子串的用户?

场景2: 表单验证

// 验证回文串:判断用户输入的优惠码是否有效
const couponCode = 'A1B2B1A';
// 如何判断这是一个回文串?

场景3: 数组去重

// API返回的数据可能有重复,需要去重
const sortedIds = [1, 1, 2, 2, 3, 4, 4, 5];
// 如何在不使用Set的情况下原地去重?

这些问题的最优解都需要用到双指针技巧。今天我们就来深入学习这个前端开发中最实用的算法技巧。

二、算法原理

什么是双指针?

双指针是指使用两个指针(索引)在数组或字符串上移动,通过协同工作来解决问题。根据移动方式不同,分为三种类型:

1. 对撞指针(相向双指针)

两个指针从两端向中间移动,常用于回文判断、两数之和等问题。

初始状态:
[1, 2, 3, 4, 5]
↑           ↑
left      right

移动过程:
[1, 2, 3, 4, 5]
    ↑     ↑
  left  right

[1, 2, 3, 4, 5]
      ↑
    left/right (相遇)

核心思想: 从两端向中间收缩,每次移动都能排除一些不可能的情况。

2. 快慢指针(同向双指针)

两个指针从同一端出发,以不同速度移动,常用于原地修改、滑动窗口等问题。

初始状态:
[0, 1, 2, 2, 3, 4]
↑
slow/fast

移动过程:
[0, 1, 2, 2, 3, 4]
↑     ↑
slow  fast

[0, 1, 2, 2, 3, 4]
    ↑        ↑
  slow      fast

核心思想: 快指针探路,慢指针维护有效区域。

3. 滑动窗口

维护一个可变长度的窗口,常用于子串查找、连续子数组等问题。

查找最长不重复子串:
"abcabcbb"
[a b c] → 窗口扩大
    ↑ ↑
    L R

"abcabcbb"
  [b c a] → 遇到重复,窗口滑动
    ↑   ↑
    L   R

核心思想: 动态调整窗口大小,维护窗口内的某种性质。

三、代码实现

1. 对撞指针 - 回文判断

/**
* 判断字符串是否为回文
* @param s - 输入字符串
* @returns 是否为回文
*/
function isPalindrome(s: string): boolean {
  // 预处理:转小写,只保留字母和数字
  const cleaned = s.toLowerCase().replace(/[^a-z0-9]/g, '');
  
  let left = 0;
  let right = cleaned.length - 1;
  
  while (left < right) {
    if (cleaned[left] !== cleaned[right]) {
      return false;
    }
    left++;
    right--;
  }
  
  return true;
}

// 测试
console.log(isPalindrome("A man, a plan, a canal: Panama")); // true
console.log(isPalindrome("race a car")); // false

关键点:

• 两个指针从两端向中间移动
• 只需比较 n/2 次
• 遇到不匹配立即返回

2. 快慢指针 - 原地去重

/**
* 删除排序数组中的重复项
* @param nums - 排序数组
* @returns 去重后的长度
*/
function removeDuplicates(nums: number[]): number {
  if (nums.length === 0) return 0;
  
  let slow = 0; // 慢指针:维护不重复元素的边界
  
  for (let fast = 1; fast < nums.length; fast++) {
    // 快指针遇到新元素
    if (nums[fast] !== nums[slow]) {
      slow++;
      nums[slow] = nums[fast]; // 将新元素放到慢指针位置
    }
  }
  
  return slow + 1; // 返回不重复元素的个数
}

// 测试
const arr = [1, 1, 2, 2, 2, 3, 4, 4, 5];
const len = removeDuplicates(arr);
console.log(arr.slice(0, len)); // [1, 2, 3, 4, 5]

关键点:

• 慢指针指向最后一个不重复元素
• 快指针负责探索新元素
• 原地修改,空间复杂度 O(1)

3. 滑动窗口 - 最长不重复子串

/**
* 找到最长不含重复字符的子串
* @param s - 输入字符串
* @returns 最长子串的长度
*/
function lengthOfLongestSubstring(s: string): number {
  const charSet = new Set<string>();
  let left = 0;
  let maxLength = 0;
  
  for (let right = 0; right < s.length; right++) {
    // 如果遇到重复字符,收缩左边界
    while (charSet.has(s[right])) {
      charSet.delete(s[left]);
      left++;
    }
    
    // 添加当前字符
    charSet.add(s[right]);
    
    // 更新最大长度
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

// 测试
console.log(lengthOfLongestSubstring("abcabcbb")); // 3 (abc)
console.log(lengthOfLongestSubstring("bbbbb"));    // 1 (b)
console.log(lengthOfLongestSubstring("pwwkew"));   // 3 (wke)

关键点:

• 右指针不断扩展窗口
• 遇到重复时,左指针收缩窗口
• 用 Set 维护窗口内字符的唯一性

4. 滑动窗口 - 固定大小窗口

/**
* 找到数组中长度为k的最大子数组和
* @param nums - 数组
* @param k - 窗口大小
* @returns 最大和
*/
function maxSumSubarray(nums: number[], k: number): number {
  if (nums.length < k) return 0;
  
  // 计算第一个窗口的和
  let windowSum = 0;
  for (let i = 0; i < k; i++) {
    windowSum += nums[i];
  }
  
  let maxSum = windowSum;
  
  // 滑动窗口
  for (let i = k; i < nums.length; i++) {
    windowSum = windowSum - nums[i - k] + nums[i];
    maxSum = Math.max(maxSum, windowSum);
  }
  
  return maxSum;
}

// 测试
console.log(maxSumSubarray([1, 4, 2, 10, 23, 3, 1, 0, 20], 4)); // 39

四、复杂度分析

时间复杂度对比

空间复杂度

• 对撞指针: O(1) - 只需要两个指针变量
• 快慢指针: O(1) - 原地修改,不需要额外空间
• 滑动窗口: O(k) - k 为窗口大小或字符集大小

为什么双指针更快?

// 暴力解法:检查所有子串是否不重复
function lengthOfLongestSubstring_bruteForce(s) {
  let maxLen = 0;
  // 枚举所有起点
  for (let i = 0; i < s.length; i++) {
    // 枚举所有终点
    for (let j = i; j < s.length; j++) {
      // 检查子串是否不重复
      if (isUnique(s, i, j)) {
        maxLen = Math.max(maxLen, j - i + 1);
      }
    }
  }
  return maxLen;
}
// 时间复杂度: O(n³)

// 双指针优化:每个字符最多被访问两次
function lengthOfLongestSubstring_optimal(s) {
  // ... (上面的实现)
}
// 时间复杂度: O(n)

五、实战应用

案例1: 防抖函数优化

/**
* 防抖函数 - 使用滑动窗口思想
*/
function debounce<T extends (...args: any[]) => any>(
  func: T,
  delay: number
): (...args: Parameters<T>) => void {
  let timeoutId: NodeJS.Timeout | null = null;
  
  return function(...args: Parameters<T>) {
    // 清除旧的定时器(相当于窗口左边界移动)
    if (timeoutId) {
      clearTimeout(timeoutId);
    }
    
    // 设置新的定时器(相当于窗口右边界移动)
    timeoutId = setTimeout(() => {
      func.apply(this, args);
    }, delay);
  };
}

// 使用场景:搜索框实时搜索
const searchInput = document.querySelector('#search');
const debouncedSearch = debounce((keyword: string) => {
  console.log('搜索:', keyword);
  // 调用API搜索
}, 300);

searchInput?.addEventListener('input', (e) => {
  debouncedSearch((e.target as HTMLInputElement).value);
});

案例2: 虚拟滚动 - 可视区域计算

/**
* 虚拟滚动 - 计算可视区域的元素索引
*/
class VirtualScroll {
  private itemHeight: number;
  private containerHeight: number;
  
  constructor(itemHeight: number, containerHeight: number) {
    this.itemHeight = itemHeight;
    this.containerHeight = containerHeight;
  }
  
  /**
  * 使用双指针思想计算可视区域
  */
  getVisibleRange(scrollTop: number, totalItems: number): [number, number] {
    // 计算起始索引(左指针)
    const startIndex = Math.floor(scrollTop / this.itemHeight);
    
    // 计算可见数量
    const visibleCount = Math.ceil(this.containerHeight / this.itemHeight);
    
    // 计算结束索引(右指针)
    const endIndex = Math.min(startIndex + visibleCount + 1, totalItems);
    
    return [startIndex, endIndex];
  }
  
  /**
  * 渲染可视区域的元素
  */
  render(scrollTop: number, data: any[]): any[] {
    const [start, end] = this.getVisibleRange(scrollTop, data.length);
    return data.slice(start, end);
  }
}

// 使用示例
const virtualScroll = new VirtualScroll(50, 600); // 每项50px,容器600px
const allData = Array.from({ length: 10000 }, (_, i) => ({ id: i }));

window.addEventListener('scroll', (e) => {
  const scrollTop = window.scrollY;
  const visibleItems = virtualScroll.render(scrollTop, allData);
  console.log('当前渲染:', visibleItems.length, '项');
});

案例3: 数据流去重

/**
* 实时数据流去重 - WebSocket消息处理
*/
class MessageDeduplicator {
  private recentIds: Set<string>;
  private queue: string[];
  private maxSize: number;
  
  constructor(maxSize: number = 1000) {
    this.recentIds = new Set();
    this.queue = [];
    this.maxSize = maxSize;
  }
  
  /**
  * 使用滑动窗口维护最近的消息ID
  */
  isDuplicate(messageId: string): boolean {
    if (this.recentIds.has(messageId)) {
      return true;
    }
    
    // 添加新ID
    this.recentIds.add(messageId);
    this.queue.push(messageId);
    
    // 窗口超过最大值,移除最旧的
    if (this.queue.length > this.maxSize) {
      const oldId = this.queue.shift()!;
      this.recentIds.delete(oldId);
    }
    
    return false;
  }
}

// WebSocket使用示例
const ws = new WebSocket('wss://example.com/messages');
const deduplicator = new MessageDeduplicator(1000);

ws.onmessage = (event) => {
  const message = JSON.parse(event.data);
  
  if (!deduplicator.isDuplicate(message.id)) {
    // 处理新消息
    console.log('新消息:', message);
  }
};

案例4: 表单验证 - 密码强度检查

/**
* 密码强度检查 - 使用滑动窗口检测连续字符
*/
interface PasswordStrength {
  score: number;
  feedback: string[];
}

function checkPasswordStrength(password: string): PasswordStrength {
  const feedback: string[] = [];
  let score = 0;
  
  // 基础检查
  if (password.length >= 8) score += 20;
  if (/[a-z]/.test(password)) score += 20;
  if (/[A-Z]/.test(password)) score += 20;
  if (/[0-9]/.test(password)) score += 20;
  if (/[^a-zA-Z0-9]/.test(password)) score += 20;
  
  // 使用滑动窗口检测连续重复字符
  let left = 0;
  for (let right = 0; right < password.length; right++) {
    if (password[right] === password[left]) {
      if (right - left >= 2) {
        score -= 10;
        feedback.push('包含连续重复字符');
        break;
      }
    } else {
      left = right;
    }
  }
  
  // 检测连续递增/递减
  for (let i = 0; i < password.length - 2; i++) {
    const code1 = password.charCodeAt(i);
    const code2 = password.charCodeAt(i + 1);
    const code3 = password.charCodeAt(i + 2);
    
    if (code2 - code1 === 1 && code3 - code2 === 1) {
      score -= 10;
      feedback.push('包含连续递增字符');
      break;
    }
  }
  
  return { score: Math.max(0, Math.min(100, score)), feedback };
}

// 测试
console.log(checkPasswordStrength("aaa123"));      // 低分
console.log(checkPasswordStrength("Abc123!@#"));   // 高分

六、练习题

题目1: 两数之和 II (LeetCode 167)

难度: 中等

题目描述: 给定一个已按升序排列的整数数组 numbers,找出两个数使得它们相加之和等于目标数 target。

/**
* @param numbers - 升序数组
* @param target - 目标和
* @return 两个数的索引(从1开始)
*/
function twoSum(numbers: number[], target: number): number[] {
  // 在这里实现你的代码
}

// 测试用例
console.log(twoSum([2, 7, 11, 15], 9));  // [1, 2]
console.log(twoSum([2, 3, 4], 6));       // [1, 3]

提示: 使用对撞指针,从两端向中间移动。

function twoSum(numbers: number[], target: number): number[] {
  let left = 0;
  let right = numbers.length - 1;
  
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    
    if (sum === target) {
      return [left + 1, right + 1]; // 题目要求索引从1开始
    } else if (sum < target) {
      left++; // 和太小,左指针右移
    } else {
      right--; // 和太大,右指针左移
    }
  }
  
  return []; // 题目保证有解,这里不会执行到
}

题目2: 最小覆盖子串 (LeetCode 76)

难度: 困难

题目描述: 给定字符串 s 和 t,找出 s 中包含 t 所有字符的最小子串。

/**
* @param s - 源字符串
* @param t - 目标字符串
* @return 最小覆盖子串
*/
function minWindow(s: string, t: string): string {
  // 在这里实现你的代码
}

// 测试用例
console.log(minWindow("ADOBECODEBANC", "ABC")); // "BANC"
console.log(minWindow("a", "a"));               // "a"
console.log(minWindow("a", "aa"));              // ""

提示: 使用滑动窗口 + 哈希表记录字符频率。

function minWindow(s: string, t: string): string {
  if (s.length < t.length) return "";
  
  // 统计t中每个字符的频率
  const need = new Map<string, number>();
  for (const char of t) {
    need.set(char, (need.get(char) || 0) + 1);
  }
  
  const window = new Map<string, number>();
  let left = 0;
  let valid = 0; // 窗口中满足条件的字符种类数
  let start = 0;
  let minLen = Infinity;
  
  for (let right = 0; right < s.length; right++) {
    const char = s[right];
    
    // 扩大窗口
    if (need.has(char)) {
      window.set(char, (window.get(char) || 0) + 1);
      if (window.get(char) === need.get(char)) {
        valid++;
      }
    }
    
    // 收缩窗口
    while (valid === need.size) {
      // 更新最小子串
      if (right - left + 1 < minLen) {
        start = left;
        minLen = right - left + 1;
      }
      
      const leftChar = s[left];
      left++;
      
      if (need.has(leftChar)) {
        if (window.get(leftChar) === need.get(leftChar)) {
          valid--;
        }
        window.set(leftChar, window.get(leftChar)! - 1);
      }
    }
  }
  
  return minLen === Infinity ? "" : s.substring(start, start + minLen);
}

题目3: 移动零 (LeetCode 283)

难度: 简单

题目描述: 给定数组 nums,将所有 0 移到数组末尾,同时保持非零元素的相对顺序。要求原地操作。

/**
* @param nums - 数组(原地修改)
*/
function moveZeroes(nums: number[]): void {
  // 在这里实现你的代码
}

// 测试用例
const arr1 = [0, 1, 0, 3, 12];
moveZeroes(arr1);
console.log(arr1); // [1, 3, 12, 0, 0]

const arr2 = [0];
moveZeroes(arr2);
console.log(arr2); // [0]

提示: 使用快慢指针,慢指针维护非零元素的边界。

function moveZeroes(nums: number[]): void {
  let slow = 0; // 慢指针:下一个非零元素应该放置的位置
  
  // 快指针遍历数组
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // 交换非零元素到前面
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }
}

七、总结与扩展

核心要点

1. 对撞指针:从两端向中间,适合有序数组、回文问题
2. 快慢指针:同向移动,适合原地修改、链表问题
3. 滑动窗口:动态调整窗口,适合子串、子数组问题

识别双指针问题的信号

• ✅ 数组/字符串是有序的
• ✅ 需要原地修改,空间复杂度要求 O(1)
• ✅ 查找满足某种条件的子串/子数组
• ✅ 需要去重、合并操作
• ✅ 问题涉及两端或区间

常见变体

进阶学习

1. 三指针问题: 三数之和、颜色分类
2. 多路归并: 合并K个排序链表
3. 双端队列: 滑动窗口最大值
4. 前缀和 + 双指针: 和为K的子数组

调试技巧

// 可视化双指针的移动过程
function debugTwoPointers(arr: number[], left: number, right: number) {
  const visual = arr.map((val, idx) => {
    if (idx === left && idx === right) return `[${val}]`;
    if (idx === left) return `L${val}`;
    if (idx === right) return `${val}R`;
    return ` ${val} `;
  });
  console.log(visual.join(''));
}

性能优化建议

1. 提前终止: 找到答案后立即返回
2. 边界检查: 避免数组越界
3. 空间换时间: 适当使用哈希表辅助
4. 预处理: 排序、去重等操作可以简化后续逻辑

下期预告

下一篇我们将学习栈与队列,探讨如何用它们解决:

• 浏览器的前进后退功能
• 表达式求值与语法解析
• 异步任务队列的实现

相关资源:

• LeetCode 双指针题单
• 可视化算法网站
• 本系列代码仓库