Skip to main content

双指针

以下是有关双指针相关算法的题目与题解。

移除元素​

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。

不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。

元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

我的解法​

var removeElement = function (nums, val) {
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] === val) {
      nums.splice(i, 1)
      i--
    }
  }

  return nums.length
}

然而 splice 操作时间复杂度为 O(n)，并且每次删除一个元素都会导致数组的重新排序。因此在算法解题中应尽量避免使用数组自带方法操作

方法: 双指针​

var removeElement = function (nums, val) {
  let left = 0,
    right = nums.length
  while (left < right) {
    if (nums[left] === val) {
      nums[left] = nums[right - 1]
      right--
    } else {
      left++
    }
  }
  return left
}

如果题目有要求排序的话，不如将符合条件(nums[i] !== val)的元素移到数组头部，这样就不需要排序了。

var removeElement = function (nums, val) {
  const n = nums.length
  let left = 0

  for (let right = 0; right < n; right++) {
    if (nums[right] !== val) {
      nums[left] = nums[right]
      left++
    }
  }

  return left
}

删除有序数组中的重复项​

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。返回 k 。

我的解法​

var removeDuplicates = function (nums) {
  const counter = {}
  let count = 0
  for (let i = 0; i < nums.length; i++) {
    counter[nums[i]] = (counter[nums[i]] || 0) + 1

    if (counter[nums[i]] > 2) {
      continue
    } else {
      nums[count] = nums[i]
      count++
    }
  }

  return count
}

思路很清晰，就是用一个计数对象来计数，然后遍历数组，如果计数大于 1，就跳过，否则就赋值。不过我这里引入了 counter 对象，因此空间复杂度为 O(k)，其中 k 表示不同元素的数量。

如果以我这个思路去解决 删除有序数组中的重复项 II 解决题目就会特别容易，只需要将 > 1 换成 1 即可。不过题目要求 不使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

并且通常哈希计数针对无序而言，而题目所给定的数据又有序，因此想要解得好就需要采用其他方案。

方法: 双指针​

由于题目声明输入 升序排列 的数组，因此采用快慢双指针来判断后一个元素是否等于前一个，如果不相等则说明是不同的元素，慢指针(不同数字次数)加一，快指针继续遍历。

var removeDuplicates = function (nums) {
  const n = nums.length

  let fast = 1,
    slow = 1
  while (fast < n) {
    if (nums[fast] !== nums[fast - 1]) {
      nums[slow] = nums[fast]
      ++slow
    }
    ++fast
  }
  return slow
}

判断子序列​

我的解法(失败)​

既然判断子序列，那我就把无关元素删除，然后判断最后元素是否包含即可。

var isSubsequence = function (s, t) {
  t = t.replace(new RegExp(`[^${s}]`, 'g'), '')
  return t.includes(s)
}

然而假设输入数据为

s = "leetcode"
t = "yyyyyleeeytcode"

处理后数据为

s = "leetcode"
t = "leeetcode"

很显然这里 includes 无法判断子序列，因此这种思路不可行。

方法: 双指针​

var isSubsequence = function (s, t) {
  let i = 0,
    j = 0
  while (i < s.length && j < t.length) {
    if (s[i] === t[j]) {
      i++
    }
    j++
  }

  return i === s.length
}

两数之和 II - 输入有序数组​

方法: 双指针​

function twoSum(nums, target) {
  let left = 0
  let right = nums.length - 1

  while (left < right) {
    const sum = nums[left] + nums[right]
    if (sum === target) {
      return [left, right]
    }

    if (sum > target) {
      right--
    } else if (sum < target) {
      left++
    }
  }
}
0%