排序双指针：三数之和与顺序匹配

排序双指针：三数之和与顺序匹配

整理来源：前端高频算法原题解析.pdf、第二篇 - 大厂面试手写题及算法.pdf、第四篇 - 面试高频踩坑解析.pdf 的算法题部分。只保留题面、算法不变量、复杂度和边界验证，已过滤课程、机构、报名信息以及无法复核的效果数字。

1. 最接近三数之和

给定数组和目标值，返回三个数之和中与目标差的绝对值最小者。先排序，固定 i，再让 left 和 right 在右侧区间内对撞：和偏小就增大 left，和偏大就减小 right。排序后的单调性使每次移动都能排除一批不可能更优的组合。

function threeSumClosest(nums, target) {
  if (nums.length < 3) {
    throw new RangeError('at least three numbers are required')
  }

  const values = [...nums].sort((a, b) => a - b)
  let best = values[0] + values[1] + values[2]

  for (let i = 0; i < values.length - 2; i += 1) {
    let left = i + 1
    let right = values.length - 1

    while (left < right) {
      const sum = values[i] + values[left] + values[right]
      if (Math.abs(sum - target) < Math.abs(best - target)) best = sum
      if (sum === target) return sum
      if (sum < target) left += 1
      else right -= 1
    }
  }

  return best
}

时间复杂度为 O(n log n + n^2)，额外空间为 O(n)（排序副本）。如果明确允许原地排序，空间可按排序实现的栈空间另行说明。题目没有规定“同样接近时”的取值时，不要自行声称存在唯一答案；上面的实现保留先遇到的结果。

2. 删除字符后匹配字典中的最长单词

判断候选单词是否为源字符串的子序列，然后按“长度更长优先、长度相同字典序更小”更新答案。下面的示例把字典序定义为 Unicode code point 顺序；如果题目采用 locale 或业务自定义排序，应注入对应比较器。候选数量不大时，对每个单词各走一遍源串最容易证明正确：

function isSubsequence(word, source) {
  const wordChars = [...word]
  let i = 0
  for (const char of source) {
    if (char === wordChars[i]) i += 1
    if (i === wordChars.length) return true
  }
  return wordChars.length === 0
}

function compareCodePointOrder(left, right) {
  const a = [...left]
  const b = [...right]
  const length = Math.min(a.length, b.length)

  for (let i = 0; i < length; i += 1) {
    const leftCode = a[i].codePointAt(0)
    const rightCode = b[i].codePointAt(0)
    if (leftCode !== rightCode) return leftCode - rightCode
  }

  return a.length - b.length
}

function findLongestWord(source, dictionary) {
  let answer = ''
  let answerLength = 0

  for (const word of dictionary) {
    if (!isSubsequence(word, source)) continue
    const wordLength = [...word].length
    if (
      wordLength > answerLength ||
      (wordLength === answerLength && compareCodePointOrder(word, answer) < 0)
    ) {
      answer = word
      answerLength = wordLength
    }
  }

  return answer
}

若源串固定且查询很多，可以为每个字符预处理出现位置，再用二分查找下一个位置；这是“重复查询优化”，不能把一次查询也误说成 O(log n)。候选遍历版本的时间复杂度约为 O(D * S + L)，D 是字典词总数，S 是源串长度，L 是候选词总字符数（展开和比较也要计入）。

3. 有序二维矩阵搜索

每行、每列递增时，从左下角开始：当前值大于目标就上移，当前值小于目标就右移。每一步排除一整行或一整列，复杂度为 O(rows + columns)，额外空间为 O(1)。

function searchSortedMatrix(matrix, target) {
  if (!Array.isArray(matrix) || matrix.length === 0) return false
  if (!Array.isArray(matrix[0]) || matrix[0].length === 0) return false

  const width = matrix[0].length
  if (matrix.some((row) => !Array.isArray(row) || row.length !== width)) {
    throw new TypeError('matrix must be rectangular')
  }

  let row = matrix.length - 1
  let column = 0

  while (row >= 0 && column < matrix[0].length) {
    const value = matrix[row][column]
    if (value === target) return true
    if (value > target) row -= 1
    else column += 1
  }

  return false
}

示例先验证矩阵是非空的矩形数组；若题目已在契约中保证矩形，可省略这段校验。题目若只保证每行有序而不保证每列有序，不能使用这个起点和移动规则，应改为逐行二分或其他模型。

4. 判断子序列

同向指针扫描长字符串 target，只要匹配到 source 的下一个字符就推进。空的 source 是任何字符串的子序列：

function isSubsequenceOf(source, target) {
  const sourceChars = [...source]
  let sourceIndex = 0

  for (const char of target) {
    if (char === sourceChars[sourceIndex]) sourceIndex += 1
    if (sourceIndex === sourceChars.length) return true
  }

  return sourceChars.length === 0
}

不要把“子序列”与“子串”混淆：子序列允许跳过字符，但相对顺序不能改变。若 target 固定、查询串很多，可为每个字符建立递增位置表，并从上一次匹配位置之后二分查找；预处理和内存成本要一起说明。

5. 分发饼干的贪心匹配

把孩子胃口和饼干尺寸都升序排列，用最小的可行饼干满足当前最小胃口。若饼干太小，跳过它不会损失最优解，因为后面的孩子胃口不更小；若可满足，则同时推进两个指针。

function findContentChildren(greed, cookies) {
  const needs = [...greed].sort((a, b) => a - b)
  const sizes = [...cookies].sort((a, b) => a - b)
  let child = 0
  let cookie = 0
  let satisfied = 0

  while (child < needs.length && cookie < sizes.length) {
    if (sizes[cookie] >= needs[child]) {
      child += 1
      satisfied += 1
    }
    cookie += 1
  }

  return satisfied
}

排序占主导，复杂度为 O(c log c + s log s)，其中 c、s 分别是孩子和饼干数量。这里的贪心目标是“满足人数最多”，若目标改为收益最大或优先级约束，必须重新证明模型。

6. 验证回文串

先明确“可比较字符”的定义。下面实现只保留 ASCII 字母和数字；如果产品需要支持 Unicode 字母，应改用明确的 Unicode 分词/规范化策略，不能把 ASCII 正则当成通用国际化方案。

function isAsciiAlphaNumeric(char) {
  return /[a-z0-9]/i.test(char)
}

function isPalindrome(text) {
  let left = 0
  let right = text.length - 1

  while (left < right) {
    while (left < right && !isAsciiAlphaNumeric(text[left])) left += 1
    while (left < right && !isAsciiAlphaNumeric(text[right])) right -= 1

    if (text[left].toLowerCase() !== text[right].toLowerCase()) return false
    left += 1
    right -= 1
  }

  return true
}

这种写法不需要先复制清洗后的字符串，额外空间为 O(1)。空字符串和没有可比较字符的字符串按题面通常视为回文，但应在回答中说清楚。

7. 从后向前合并有序数组

当第一个数组尾部已经预留空间时，从后向前写入，避免覆盖尚未读取的有效元素：

function mergeInto(left, leftLength, right) {
  let i = leftLength - 1
  let j = right.length - 1
  let write = leftLength + right.length - 1

  while (j >= 0) {
    if (i >= 0 && left[i] > right[j]) left[write--] = left[i--]
    else left[write--] = right[j--]
  }

  return left
}

时间复杂度为 O(m + n)，额外空间为 O(1)。若题目没有预留空间，返回新数组与原地合并是两个不同契约，先确认再写代码。

常见误区与验证清单

• 先确认排序是否允许修改输入；不确定时复制。
• 双指针移动必须由单调性或不变量支撑，不能凭“看起来更接近”跳过候选。
• 比较链表相交时比较节点引用，比较字符串题时明确大小写、空白和 Unicode 规则。
• 至少测试空输入、单元素、重复值、全都不匹配、刚好命中、答案在边界和极端顺序。
• 口述复杂度时把排序、预处理、输出结果和递归/临时空间分别计入。

相关专题：双指针基础知识速览、贪心：区间问题、滑动窗口：字符覆盖。