【LeetCode 03】双指针法总结-阿里云开发者社区

【LeetCode 03】双指针法总结

2024-10-14 10

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 【LeetCode 03】双指针法总结

一、适用条件

适用条件为：

数组问题
链表问题
数组与链表中涉及到元素覆盖、删除的问题（移除重复、相同元素）
如【LeetCode 27】：给你一个数组 nums 和一个值 val，你需要原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并原地修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

二、方法总结

双指针法又叫做快慢指针法。包括快指针和慢指针。

slowIndex慢指针
fastIndex快指针

两个指针在一个for循环内完成两个for循环的工作。for1+for2=for。

step1：初始化快慢指针

step2：快指针遍历，当快指针遍历值与val值不同时，快指针覆盖前面慢指针所指的值

for(int fastIndex=0;fastIndex<size;fastIndex++){
    if(nums[fastIndex]!=val)
      nums[slowIndex++]=nums[fastIndex];
}

step3：返回慢指针

三、双指针法具体案例

根据例题：

int removeElement(int* nums, int numsSize, int val){
   int slowIndex=0;//step1
     for(int fastIndex=0;fastIndex<numsSize;fastIndex++){//step2
         if(nums[fastIndex]!=val)
           nums[slowIndex++]=nums[fastIndex];
     }
    return slowIndex;//step3
}