烂大街的算法碎片集

algorithm_fragment.md

更新索引时跳过重复数据

• 输入：一个 有序 的 数字数组
• 目标：遍历时跳过重复值

如果需要在遍历一个数组时跳过临近的相同值, 可以使用常规的 while 循环来替换 for 循环, 并在内部使用一个特殊的 while 表达式来更新索引

不同于直接的 i++ , 而是将 i++ 改为 ++i , 再将其放在 while 循环中, 并不断将其值与上一个元素或下一个元素比较来确定是否仍在重复区内

由于数组为有序，因此重复的字符串都应该处于一起，将其作为 while 停止的条件, 则可以在索引被移出重复区域时自动停止

假设

变量 s 指代一个已排序的数组

需要在遍历时做某些操作，且跳过重复项

• 常规遍历

for (let index=0; index<s.length; index++) {
  // DO SOMETHING ...
}

• 跳过重复索引遍历

// 使用 while 循环是为了能手动操作 index
let index = 0
while(index<=s.length-1) {
  // DO SOMETHING ...
  // 如果 index 还未到达目标数组的末尾，则将 index 加 1，并计算与上一个元素是否相同，如果不同则继续运算，直到跳过重复项
  while (index<s.length-1 && s[index]===s[++index]) {}
  // 这个表达式也可以写为如下形式，这样看起来较为直观，但多了一步减法计算
  // do { index++ } while(index<s.length-1 && s[index-1]===s[index])
}

双指针遍历法

• 输入：一个 有序 的 数字数组
• 目标：在一个 有序 的 数字数组中找到找到 两个 与目标数字相关的元素

如果需要在输入中找到 两个 符合特定条件的对象，可以使用双指针遍历法快速遍历

不同于常规的双循环嵌套遍历的顺序查找，双指针在每次查找时都可以有效利用已排序数组的顺序特性

通过与目标条件的比较，在每次迭代通过左移右侧指针或右移左侧指针来调整结果集的大小以快速趋近结果，从而快速找到目标对象组合

假设

变量 s 指代一个已排序的数组

需要找到符合 a + b = MAGIC_NUMBER 的数

• 双循环嵌套遍历

// 两个嵌套遍历数组
s.forEach((current, index) => {
  for (let i = index+1; i<s.length-1; i++) {
    const sum = current + s[i]
    if (sum===MAGIC_NUMBER) {
      // DO SOMETHING ...
    }
  }
})

• 双指针遍历

// 初始化两侧指针, 一个在头，一个在尾
let leftPointer = 0
let rightPointer = s.length-1
do {
  // 计算结果
  const sum = s[leftPointer] + s[rightPointer]
  if (sum===MAGIC_NUMBER) {
    // DO SOMETHING ...
  }
  // 更新指针
  if (sum<=MAGIC_NUMBER) {
    // 计算结果小于目标，左侧指针右移以增大结果集
    leftPointer++
    // 如果不需要遍历重复项，此处也可以使用 while 循环跳过重复数据)
    // while (leftPointer<rightPointer && s[leftPointer]===s[++leftPointer]) {}
  } else {
    // 计算结果大于目标，右侧指针左移以减小结果集
    rightPointer--
    // 如果不需要遍历重复项，此处也可以使用 while 循环跳过重复数据
    // while (leftPointer<rightPointer && s[rightPointer]===s[--rightPointer]) {}
  }
} while(leftPointer < rightPointer)