双指针

双指针风骚起来，也是无敌

双指针 :relaxed: O(n)

要知道数组的元素在内存地址中是连续的，不能单独删除数组中的某个元素，只能覆盖。
双指针法（快慢指针法）： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

定义快慢指针

快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
慢指针：指向更新 新数组下标的位置

leetcode 27 移除元素

题目

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

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

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

code

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) 
        {
            if (val != nums[fastIndex]) 
            {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

leetcode 26 删除有序数组中的重复项

题目

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

code

class Solution {
public:
    int removeDuplicates(vector<int>& nums) 
    {
        int fast_index = 1;
        int slow_index = 0;
        while (fast_index < nums.size())
        {
            if (nums[fast_index] != nums[slow_index])
            {
                nums[++slow_index] = nums[fast_index];  //先执行自增操作
            }
            fast_index++;
        }
        return slow_index + 1;
        //因为fast_index = 1,所以默认第一个元素是在数组中的，相当于少运行了一次slow_index++,因此结果要 slow_index + 1
    }
};

想法 :blush:

//关于slow_index + 1 的理解
//对于普通的移除元素而言，有多少 nums[fastIndex] != val slowIndex就等于几，数组长度等于slow_index
//而对于此题，同样有多少 nums[fast_index] != nums[slow_index] slowIndex就等于几，但是因为fastIndex = 1,相当于少计算了第一个一个数组，因此数组长度=slowIndex + 1

leetcode 844 比较含退格的字符串

题目

给定 s 和 t 两个字符串，当它们分别被输入到空白的文本编辑器后，如果两者相等，返回 true 。# 代表退格字符

code

class Solution {
public:
    string deal_backspace(string str)
    {
        int fast = 0;
        int slow = 0;
        while (fast < str.size())
        {
            if (str[fast] != '#')
            {
                str[slow++] = str[fast];
            }
            else if(slow > 0)   //防止超出范围
            {
                slow--;
            }
            fast++;
        }
        return str.substr(0, slow);//字符截取函数
    }

    bool backspaceCompare(string s, string t)
    {
        return deal_backspace(s) == deal_backspace(t);
    }
};

想法 :smiley:

• 要注意数组不要越界
• string类型的数据可以像数组一样用 [ ] 对其中的元素操作