算法入门-2 双指针

学习日志

概述

在数组和链表的问题里经常考察的两类问题：「滑动窗口」和「双指针」，其实「滑动窗口」也可以称为「双指针」。

循环不变量

循环前、中、后保持不变

「循环不变量」不是很高深的概念，在「算法」和「数据结构」的世界里，到处都有它的身影。

「循环不变量」是指我们在编写代码的过程中，要一直循序不变的性质，这样的性质是根据要解决的问题，由我们自己定义的。「循环不变量」是我们写对一个问题的基础，保证了在「初始化」「循环遍历」「结束」这三个阶段相同的性质，使得一个问题能够被正确解决。

力扣 27.移除元素

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int left = 0;
        int n = nums.size();
        int right = n - 1;
        while (left <= right) {
            if (nums[left] == val) {
                nums[left] = nums[right];
                right--;
            } else {
                left++;
            }
        }

        return left;
    }
};

参考文章:
滑动窗口和双指针-力扣