双指针经典题目

删除重复项

一个有序数组 nums ，原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度（注意：不能使用额外的数组空间，必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成）

示例:

例:输入: [0,1,2,2,3,3,4]
   输出: 5

思路: 在有序数组中，设置快慢指针 quick 和 slow ，只要 nums[quick] = nums[slow] 时，增加 quick 跳过重复项，如果 nums[quick] != nums[slow] 时，将 nums[quick] 赋值给 nums[++slow] ,接着再次重复的过程，知道 quick 到达数组的末尾位置。

:::details 点击查看代码

function unique(nums){
  if(!nums||!nums.length){
    return 0
  }
  let slow=0;
  for(let quick=1;quick<nums.length;quick++){
    if(nums[quick]!=nums[slow]){
      nums[++slow]=nums[quick];
    }
  }
  return slow+1
}

let array=[0,1,1,1,2,2,2,2,3,3,3,3,3];
console.log(unique(array));

:::

删除指定值元素

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

示例1:

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2]
解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。

示例2:

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3]
解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

思路:

• 定义双指针

  • left: 指向下一个将要赋值的位置
  • right: 指向当前将要处理的元素

• 处理 nums 元素

  • 如果右指针指向的元素不等于 val，它一定是输出数组的一个元素，我们就将右指针指向的元素复制到左指针位置，然后将左右指针同时右移；
  • 如果右指针指向的元素等于 val，它不能在输出数组里，此时左指针不动，右指针右移一位。

整个过程保持不变的性质是：区间 [0,left) 中的元素都不等于 val。当左右指针遍历完输入数组以后，left 的值就是输出数组的长度。

:::details 点击查看代码

function remove(nums,val){
  let len=nums.length;
  if(len==0){
    return 0
  }
  let slow=0;
  for(let quick=0;quick<len;quick++){
    if(nums[quick]!=val){
      nums[slow++]=nums[quick];
    }
  }
  return slow
}

// const nums= [3,2,2,3];
const nums=[0,1,2,2,3,0,4,2];
console.log(remove(nums,2));

:::

寻找数组的中心索引

给定一个整数数组 nums ，请编写一个能够返回数组中心下标的方法（中心下标是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和）

思路: 先统计除整个数组的总和 sum ，然后从第一个元素开始叠加 total。总和 sum 递减当前元素, total 叠加递增当前元素。直到两个值相等

:::details 点击查看代码

function center(nums){
  let sum=nums.reduce((prev,curr)=>{
    return prev+curr
  },0)
  let total=0;
  for(let i=0;i<nums.length;i++){
    total+=nums[i];
    if(total==sum){
      return i
    }else{
      sum-=nums[i];
    }
  }
  return -1
}
let array=[1,7,3,6,5,6];
console.log(center(array));

:::

取斐波那契

求取斐波那契数列第 N 位的值

:::details 点击查看双指针迭代代码

function fibonacciSequenceK(num){
  if(num==0){
      return 0
    }
    if(num==1){
      return 1
    }
    let first=0;
    let second=1;
    for(let i=2;i<=num;i++){
      let sum=first+second;
      first=second;
      second=sum;
    }
    return second
}
console.log(fibonacciSequenceK(8));

:::

反转数组

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。

示例1:

输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例2:

输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

思路:

• 将 left 指向字符数组首元素，right 指向字符数组尾元素。
• 当 left < right：
  • 交换 s[left] 和 s[right]；
  • left 指针右移一位，即 left = left + 1；
  • right 指针左移一位，即 right = right - 1。
• 当 left >= right，反转结束，返回字符数组即可。

:::details 点击查看代码

function reverse(array){
  let left=0;
  let right=array.length-1;
  while(left<right){
    [array[left],array[right]]=[array[right],array[left]];
    left++;
    right--;
  }
}
const array=["h","e","l","l","o"];
reverse(array);
console.log(array);

:::

最大连续数

给定一个二进制数组， 计算其中最大连续 1 的个数。

示例:

输入：[1,1,0,1,1,1]
输出：3
解释：开头的两位和最后的三位都是连续 1 ，所以最大连续 1 的个数是 3.

思路:

• 定义双指针
  • maxCount: 最大的连续个数
  • count: 当前的连续个数
• 遍历 nums 数组

:::details 点击查看代码

function maxContinuous(nums){
  let maxCount=0;
  let count=0;
  for(let i=0;i<nums.length;i++){
    if(nums[i]==1){
      count++
    }else{
      maxCount=Math.max(maxCount,count);
      count=0;
    }
  }
  maxCount=Math.max(maxCount,count);
  return maxCount;
}

const nums=[1,1,0,1,1,1];
console.log(maxContinuous(nums));

:::

移动零

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

注意:

• 必须在原数组上操作，不能拷贝额外的数组。
• 尽量减少操作次数。

示例:

输入: [0,1,0,3,12]
输出: [1,3,12,0,0]

思路:使用双指针，左指针指向当前已经处理好的序列的尾部，右指针指向待处理序列的头部。右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。

注意到以下性质:

• 左指针左边均为非零数；
• 右指针左边直到左指针处均为零。

因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

:::details 点击查看代码

function moveZero(nums){
    let len=nums.length;
    let left=0;
    let right=0;
    while(right<len){
        if(nums[right]!=0){
            [nums[left],nums[right]]=[nums[right],nums[left]];
            left++
        }  
        right++ 
    }
    return nums
}

const nums=[0,1,0,3,12];
console.log(moveZero(nums));

:::

性能分析:

• 时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。

• 空间复杂度：O(1)。只需要常数的空间存放若干变量。