24届秋招专场 · 数组如何用双指针解题呢？

文章目录

• 删除有序数组中的重复项
• 删除排序链表中的重复元素
• 移除元素
• 移除零

大家好，近期主要更新数组相关的解题算法咯，感兴趣的老铁可以一起看过来啦。

今天更新使用双指针解决数组部分题型，注意哦，这里所说的双指针不是C语言中“指针”的概念，指的是数组的索引下标，不要混淆咯。

话不多说，开始刷题！

删除有序数组中的重复项

题目链接：删除有序数组中的重复项 题目描述：

解题思路：

• 定义快慢指针，slow走在后面，fast走在前面探路
• fast找到不重复的元素就赋值给slow，并且slow++
• PS：赋值和slow++的先后顺序请画图理解

代码详解：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        // 定义快慢指针，slow走在后面，fast走在前面探路
        // fast找到不重复的元素就赋值给slow，并且slow++
        // 需要注意赋值和slow++的先后顺序，需要画图去理解
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[slow] != nums[fast])
            {
                slow++; // slow++在先，后赋值
                nums[slow] = nums[fast];
            }

            fast++;
        }

        // 光看没用，请画图理解
        return slow + 1;
    }
};

理解了上面的数组题型，下面的链表就不难理解啦，只需要注意这里指针的指向即可。

删除排序链表中的重复元素

题目链接：删除排序链表中的重复元素 题目描述：

解题思路：

仿照上面的解题思路即可，最后需要注意断开与后面重复元素的连接。

代码详解：

class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) 
    {
        if(head == nullptr)
            return nullptr;

        // 定义快慢指针
        ListNode* slow = head, *fast = head;

        while(fast != nullptr)
        {
            if(slow->val != fast->val)
            {
                slow->next = fast;
                slow = slow->next;
            }

            fast = fast->next;
        }

        // 注意需要断开与后面重复元素的连接
        slow->next = nullptr;

        return head;
    }
};

移除元素

题目链接：移除元素 题目描述：

解题思路：

定义快慢指针，fast遇到值不为val的元素就赋值给slow，并且slow++，请注意赋值和slow++的先后顺序，需要画图理解。

代码详解：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) 
    {
        // 定义快慢指针
        // 如果fast遇到值不为val的元素则赋值给slow，并且slow++
        // 还是需要注意赋值和slow++的先后顺序，请画图理解
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};

移除零

题目链接：移除零 题目描述：

解题思路：

• 根据 移除元素 思路，将0全部移除，此时数组前面的元素都是非0数
• 然后再将[p, nums.size()-1]全部置为0即可

代码详解：

class Solution {
public:
    void moveZeroes(vector<int>& nums) 
    {
        // 根据 移除元素 思路，将0全部移除
        // 然后再将[p, nums.size()-1]全部置为0即可
        int p = removeElement(nums, 0);

        for(int i = p; i < nums.size(); i++)
        {
            nums[i] = 0;
        }
    }

    // 移除元素
    int removeElement(vector<int>& nums, int val)
    {
        int slow = 0, fast = 0;

        while(fast < nums.size())
        {
            if(nums[fast] != val)
            {
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }

        return slow;
    }
};