双指针技巧秒杀七道数组题目

• 快慢双指针
• 左右双指针
• 扩散双指针

167. 两数之和 II - 输入有序数组 (opens new window)

// 左右指针
var twoSum = function (numbers, target) {
  // 方式1 暴力 时间 O(n2) 空间O(1)
  // for (let i = 0; i < numbers.length; i++) {
  //     for (let j = i+1; j < numbers.length;j++ ) {
  //         if(numbers[i]+numbers[j] === target) {
  //             return [i+1, j+1]
  //         }
  //     }
  // }
  // 方式二 首位双指针 时间 O(n) 空间O(1)
  let start = 0
  let end = numbers.length - 1

  while (start < end) {
    if (numbers[start] + numbers[end] > target) {
      end--
    } else if (numbers[start] + numbers[end] < target) {
      start++
    } else {
      return [start + 1, end + 1]
    }
  }
}

26. 删除有序数组中的重复项 (opens new window)

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  // 升序 原地删除 快慢指针 遇到与slow不一样的元素的时候 fast移动 slow移动 修改slow的值
  let slow = 0
  let fast = 0
  while (fast < nums.length) {
    if (nums[slow] === nums[fast]) {
      fast++
    } else {
      let diff = nums[fast]
      slow++
      nums[slow] = diff
      fast++
    }
  }
  return slow + 1
}

::: Tip 数组的原地删除可以通过调换位置实现 :::

27. 移除元素 (opens new window)

/**
 * @param {number[]} nums
 * @param {number} val
 * @return {number}
 */
var removeElement = function(nums, val) {
    // 数组的原地操作 快指针的目的：找到目标元素 慢指针：找到填入的位置
    let slow = 0
    let fast = 0
    while (fast < nums.length) {
        if (nums[fast] === val) {
            fast++
        } else {
            nums[slow] = nums[fast]
            slow++
            fast++
        }
    }
    return slow

283. 移动零 (opens new window)

var moveZeroes = function (nums) {
  const n = nums.length
  let left = 0
  for (let right = 0; right < n; right++) {
    if (nums[right] !== 0) {
      ;[nums[left], nums[right]] = [nums[right], nums[left]]
      left++
    }
  }
  return left
}

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
  let slow = 0
  let fast = 0
  while (fast < nums.length) {
    if (nums[fast] === 0) {
      fast++
    } else {
      // 这里做一个调换 而不是直接赋值
      const tmp = nums[slow]
      nums[slow] = nums[fast]
      nums[fast] = tmp
      slow++
      fast++
    }
  }
  return nums
}

344. 反转字符串 (opens new window)

var reverseString = function (s) {
  let left = 0
  let right = s.length - 1

  while (left < right) {
    ;[s[left], s[right]] = [s[right], s[left]]
    left++
    right--
  }
  return s
}

5. 最长回文子串 (opens new window)

/**
 * @param {string} s
 * @return {string}
 */
var longestPalindrome = function (s) {
  // let max = 0
  // let res = ''
  // // 最长 回文 暴力解法
  // for (let i = 0; i < s.length; i++) {
  //     for (let j = i ;j<s.length;j++){
  //         if (isPalindrome(s,i,j)){
  //            if (j-i>=max){
  //                max = j-i
  //                res = s.substring(i,j+1)
  //            }
  //         }
  //     }
  // }
  // return res
  // 双指针中心扩散
  let res = ''
  for (let i = 0; i < s.length; i++) {
    const s1 = palindRome(s, i, i)
    const s2 = palindRome(s, i, i + 1)
    res = s1.length > res.length ? s1 : res
    res = s2.length > res.length ? s2 : res
  }
  return res
}

const palindRome = (s, left, right) => {
  while (left >= 0 && right < s.length && s[left] === s[right]) {
    left--
    right++
  }
  // left 和 right 多加了一次1
  return s.substring(left + 1, right)
}
const isPalindrome = (s, left, right) => {
  while (left < right) {
    if (s[left] === s[right]) {
      left++
      right--
    } else {
      return false
    }
  }
  return true
}