关于双指针的思想总结

最近再刷 leetcode上的题目的时候 我发现 双指针的应用 十分广泛。像反转数组  反转字符串 定点删除  合并数组  等等 很多 问题 双指针真的很实用。

下面我将 针对我近期遇到的题目做一个简单的总结：

1.移除元素  

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

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

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-element
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 这里我们用具体的例子 来做分析 ：

假设给你一个数组 nums = {0，1，2，2，3，0，4，2} ，val  = 2；

有两种解法 第一种是官方解法  第二种是 我的方法 很明显 我很菜 我的代码更垃圾。

#include<stdio.h>

int main()
{
    int nums[] = { 0,1,2,2,3,0,4,2 };
    int numsSize = 8;
    int val = 2;
    int count = 0;
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        if (val == nums[i])
        {
            count++;
        }
    }    //  找出 val 的个数
         //  方便 修改 打印的数字的个数


    int left = 0;
    int right = 0;   //设置快慢下标 right 是快下标 left 是慢下标

    while (right < numsSize) 
    {
        if (nums[right] != val)
        {
            nums[left] = nums[right];
            right++;
            left++;
        }
        else
        {
            right++;
        }
    }
    
    for (i = 0; i < numsSize - count; i++)
    {
        printf("%d ", nums[i]);
    }
	return 0;
}

 

#include<stdio.h>

int main()
{
    int nums[] = { 0,1,2,2,3,0,4,2 };
    int numsSize = 8;
    int val = 2;

    int count = 0;
    int i = 0;
    for (i = 0; i < numsSize; i++)
    {
        if (val == nums[i])
        {
            count++;
        }
    }   //  找出 val 的个数
        //  方便 修改 打印的数字的个数

    if (count == numsSize)  // 如果整个数组都是 val 的话 直接结束
        return 0;
    else
    {
        int end1 = numsSize - 1;        //  设置 快慢 下标 
        int end2 = numsSize - count - 1;  //  让快下标 指向 剔除数字的数组的尾标 

        while (end1 !=  (numsSize - count - 1) ) //当慢下标 等于 剔除数字的数组的尾标 为止
        {
            if (nums[end2] == val)     // 如果 快下标指向 val 后 
            {
                if (nums[end1] != val)  // 并且 慢下标不等于val 的时候
                {                        // 把 慢下标的值赋给 快下标
                    nums[end2] = nums[end1];    // 快慢  下标减减
                    if (end2 > 0)
                        end2--;
                    else
                        return numsSize - count;
                    end1--;
                }
                else         // 如果慢下标这里 也等于 val 的时候 就把慢下标减减  
                {
                    end1--;
                }
            }
            else            //如果快下标的值不等于 val 的时候 要对快下标减减 
                            //并且要注意 快下标不能为负数
            {
                if (end2 == 0)
                {
                    return numsSize - count;
                }
                else
                    end2--;
            }
        }
    }

    // 循环打印结果 
    for (i = 0; i < numsSize - count; i++)
    {
        printf("%d ", nums[i]);
    }
	return 0;
}

2.删除有序数组中的重复项

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

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

同样这里也是利用快慢指针的思想来解题目 比较 方便

这里我们用具体的例子 来做分析 ：

假设给你一个数组 nums = {0，0，1，1，1，2，2，3，3，4}

 设置快慢下标  遇到重复数字 是快慢下标的分界点

首先当    nums[end1] == nums[end2]   的时候 对 end1 ++；直到变成这样

 

当 nums[end1]  != nums[end2]  的时候 对 end2++ 之后 把 end1 里的值赋给 end2  再对 end1++；

变成这样

这个时候 nums[end1] == nums[end2] 我们 可以继续写个 循环

while(end1 < numsSize)
   {
       if(nums[end1] == nums[end2])
       {
           ++end1;
       }
       else
       {
           nums[++end2] = nums[end1++];
       }
   }

       然后接下来：

 

 

 此时 结束循环 返回  end2 的长度 就可以了。

3.删除有序数组中的重复项 Ⅱ

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

这一题 与上一题的区别 就是 这一题 可以保存两个重复的元素

像这样

nums = [1,1,1,2,2,3] 返回  nums = [1,1,2,2,3]

nums = [0,0,1,1,1,1,2,3,3] 返回  nums = [0,0,1,1,2,3,3]

同样使用 双指针的思想 ；

回顾上一题 一个数字只能出现一次 中我们的  快下标  是和 慢下标进行比较  的 从而确定 一个数字只能出现一次

这一题 里 我们 的数字允许出现两次 这是不是 意味着 我们 的 快下标不能 再和 慢下标进行比较了

我们的快下标要和（慢下标-2）的数字进行比较 

当 快下标 指向的 数字 等于 慢下标 - 2 指向的数字 的时候  快下标++；慢下标不进行++操作；

当 快下标 指向的 数字 不等于 慢下标 - 2 指向的数字 的时候  把快下标的 值赋给 慢下标；再把快下标++；慢下标也要++；

代码化：

    int end1 = 0,end2 = 0;
    while(end1 < numsSize)
    {
       if(end2<2||nums[end2-2] != nums[end1])
       {
           nums[end2] = nums[end1];
           end2++;
           end1++;
       }
       else if(nums[end2-2] == nums[end1])
       {
           end1++;
       }
    }

 此时 结束循环 返回  end2 的长度 就可以了。

4.合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-sorted-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

例如：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3  

输出： [1,2,2,3,5,6]

这里 使用的一样是双指针的思想 但是又有不同的地方 这里 设置三个下标 像这样：

  

 代码化为：

    int end1 = m -1;
    int end2 = n -1;
    int i = m+n -1;
    while(end1 >= 0 && end2 >= 0)
    {
        if(nums1[end1]>nums2[end2])
        {
            nums1[i] = nums1[end1];
            --i;
            --end1;
        }
        else
        {
            nums1[i] = nums2[end2];
            --i;
            --end2;
        }
    }

其实上述代码还有一定的问题 没有考虑全面 思考一下 如果当 end1 小于零 跳出循环了怎么办？

 此时 跳出循环的时候 应该是这样的：

 这时 并没有达到想要的效果；优化一下 可以将 第二个数组剩余的元素直接 放到第一个 数组中

代码化：

    while(end2>=0)
    {
        nums1[end2] = nums2[end2];
        end2--;
    }   

 到此结束了；以后遇到经典题目的时候 我再来补充；2022 7-28；