以下是有关双指针相关算法的题目与题解。
移除元素
给你一个数组 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++
}
}
}