• 什么是对撞指针？

    • 初识
    • 算法图
    • 对撞过程图

  • JavaScript中的Array与对撞指针

    • 在js中，如何定义对撞指针？
    • 实现一个最简对撞指针

  • leetcode 对撞指针 解法题目

    • 7.整数反转（easy）
    • 9.回文数（easy）
    • 27.移除元素（easy）
    • 125.验证回文串（easy）
    • 167.两数之II-输入有序数组（easy）
    • 190.颠倒二进制位（easy）
    • 344.反转字符串（easy）
    • 345.反转字符串中的元音字母（easy）
    • 11.盛水最多的容器（medium）

什么是对撞指针？

初识

  • 对撞指针是双指针算法之一。
  • 对撞指针从两端向中间迭代数组。一个指针从始端开始，另一个从末端开始。
  • 对撞指针的终止条件是两个指针相遇。
  • 对撞指针常用于排序数组。

算法图

对撞过程图

167.两数之II-输入有序数组（easy）的对撞过程图。
蓝色指针：头指针 红色指针：尾指针 终止条件：头尾指针对撞

JavaScript中的Array与对撞指针

在js中，如何定义对撞指针？

命名

头尾指针的命名可以为：

  • i, j
  • head, tail
  • start, end
初始值
  • 头指针：0
  • 尾指针：数组长度减一
let arr = [1, 7, 5, 2];let head = 0;let tail = arr.length -1;

实现一个最简对撞指针

var arr = new Array(10).fill(0).map((num,i)=>num+i);var i =0;var j = arr.length - 1;while(i<j){  i++;  j--;}var collision = [i - 1, j + 1]var tip = `Array's head and tail had a collision between ${collision[0]} and ${collision[1]}`;console.log(tip); // Array's head and tail had a collision between 4 and 5

leetcode 对撞指针 解法题目

  • 7.整数反转（easy）
  • 9.回文数（easy）
  • 27.移除元素（easy）
  • 125.验证回文串（easy）
  • 167.两数之II-输入有序数组（easy）
  • 190.颠倒二进制位（easy）
  • 344.反转字符串（easy）
  • 345.反转字符串中的元音字母（easy）
  • 11.盛水最多的容器（medium）

7.整数反转（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var reverse = function (x) {  /**   * 解法2.指针对撞法   * 性能：96 ms 35.38% 35.9 MB 77.35%   */  var sign = Math.sign(x);  var arr = x.toString().split("");  //  if (sign === -1) {    arr.shift();  }  // 指针对撞开始  var i = 0;  var j = arr.length - 1;  while (i < j) {    swap(arr, i, j);    i++;    j--;  }  function swap(arr, i, j) {    var temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;  }  // 指针对撞结束  var rX = parseInt(arr.join(""));  var result = sign * rX;  var min = -Math.pow(2, 31);  var max = Math.pow(2, 31) - 1;  if (rX < min || rX > max) return 0;  return result;};

9.回文数（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var isPalindrome = function (x) {  /**   * 解法3：对撞指针法   * 性能：244ms 45.5MB   */  var strArr = `${x}`.split("");  var i = 0;  var j = strArr.length - 1;  while (i < j) {    if (strArr[i] !== strArr[j]) {      return false;    }    i++;    j--;  }  return true;};

27.移除元素（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var removeElement = function (nums, val) {  /**   * 解法2：对撞指针   * 性能：64ms 33.9MB   */  var i = 0;  var j = nums.length - 1;  while (i <= j) {    if (nums[i] === val) {      nums.splice(i, 1);      j--;    } else if (nums[j] === val) {      nums.splice(j, 1);      j--;    } else {      i++;    }  }  return nums.length;};

125.验证回文串（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var isPalindrome = function (s) {  /**   * 解法1：正则 + 对撞指针   * 性能：76ms 89.76% 37.5MB 70.83%   */  var parlinDrome = s.replace(/[^\w]/g, "").replace(/_/g, "").toLowerCase();  var strArr = parlinDrome.split("");  var i = 0;  var j = strArr.length - 1;  while (i < j) {    if (strArr[i] !== strArr[j]) {      return false;    }    i++;    j--;  }  return true;};

167.两数之II-输入有序数组（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var twoSum = function (numbers, target) {  /**   * 解法2：对撞指针   * 性能：68ms 71.18% 35.2MB 76.60%   * 时间复杂度：O(n^2)   */  var left = 0;  var right = numbers.length - 1;  while (left < right) {    if (numbers[left] + numbers[right] === target) {      return [left + 1, right + 1];    } else if (numbers[left] + numbers[right] > target) {      right--;    } else {      left++;    }  }};

190.颠倒二进制位（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

/** * @param {number} n - a positive integer * @return {number} - a positive integer */var reverseBits = function (n) {  /**   * 解法1：转数组后对撞交换位置   * 性能：76ms 35.8MB   * 思路：   * 十进制转二进制：toString(2)   * 32位空位补0：padStart(32,0)   * 反转算法：对撞指针法   * 二进制转十进制：parseInt(,2)   */  let arr = n.toString(2).padStart(32, 0).split("");  let head = 0;  let tail = arr.length - 1;  while (head < tail) {    swap(arr, head, tail);    head++;    tail--;  }  function swap(arr, i, j) {    let temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;  }  let result = parseInt(arr.join(""), 2);  return result;};

344.反转字符串（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var reverseString = function (s) {  /**   * 解法2：对撞指针   */  var headIdx = 0;  var tailIdx = s.length - 1;  while (headIdx < tailIdx) {    swap(s, headIdx, tailIdx);    headIdx++;    tailIdx--;  }  function swap(arr, i, j) {    var temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;  }  return s;};

345.反转字符串中的元音字母（easy）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

/** * @param {string} s * @return {string} */var reverseVowels = function (s) {  /**   * 解法1：对撞指针   * 性能：108 ms 31.59% 38.4 MB 66.67%   */  var univocalic = ["a", "e", "i", "o", "u", "A", "E", "I", "O", "U"];  var sArr = s.split("");  var head = 0;  var tail = sArr.length - 1;  while (head < tail) {    if (univocalic.includes(sArr[head]) && univocalic.includes(sArr[tail])) {      swap(sArr, head, tail);      head++;      tail--;    } else if (!univocalic.includes(sArr[head])) {      head++;    } else if (!univocalic.includes(sArr[tail])) {      tail--;    }  }  function swap(arr, i, j) {    var temp = arr[i];    arr[i] = arr[j];    arr[j] = temp;  }  return sArr.join("");};

11.盛水最多的容器（medium）

题目：https://leetcode-cn.com/probl...
题解：https://github.com/FrankKai/l...

var maxArea = function (height) {  /**   * 解法1：对撞指针法   * 性能：64ms 35.6MB   * */  var head = 0;  var tail = height.length - 1;  var maxCapacity = 0;  while (head < tail) {      maxCapacity = Math.max(Math.min(height[head], height[tail]) * (tail - head), maxCapacity)      if (height[head] < height[tail]) {          head++      } else {          tail--;      }  }  return maxCapacity;};

期待和大家交流，共同进步，欢迎大家加入我创建的与前端开发密切相关的技术讨论小组：

  • 微信公众号： 生活在浏览器里的我们 / excellent_developers
  • Github博客: 趁你还年轻233的个人博客
  • SegmentFault专栏：趁你还年轻，做个优秀的前端工程师
  • Leetcode讨论微信群：Z2Fva2FpMjAxMDA4MDE=（加我微信拉你进群）

努力成为优秀前端工程师！