双指针法是一种在遍历对象时使用两个指针进行扫描的方法，通常这两个指针可以是相同方向移动（同向移动），也可以是相反方向移动（相向移动）。

常见的使用场景包括：

有序数组中查找两个数的和等于目标值：通过将数组排序，然后使用两个指针，一个指向数组的开头，另一个指向数组的结尾，再将两个指针相向移动，根据两指针所指元素之和与目标值的大小关系来移动指针，直到找到满足条件的两个数或者确定不存在这样的配对。
有序链表中查找两个数的和等于目标值：与在有序数组中的操作类似。
数组去重：先将数组排序，使相同的数紧挨在一起。然后定义两个指针 i 和 j，初始都指向数组起始位置，i 指针遍历整个数组，j 指针始终指向当前不重复部分的最后一个数。当 i 指针指向的元素不等于 j 指针指向的元素时，将 i 指针指向的元素复制到 j 的下一个位置，并移动 j 指针。
反转字符串或链表：定义两个指针分别指向字符串的头和尾（或链表的头和尾节点），然后交换两个指针所指的元素（或节点），直到两个指针相遇。
删除链表的倒数第 n 个节点：定义两个指针，先让一个指针（fast）向前移动 n 步，然后再同时移动两个指针（fast 和 slow），直到 fast 指针到达链表末尾，此时 slow 指针所指的就是要删除的节点的前一个节点。
判断链表是否存在环：使用快慢两个指针，快指针每次移动两步，慢指针每次移动一步。如果链表中存在环，快指针最终会追上慢指针；否则快指针会先到达链表尾部。
滑动窗口：常见于在数组或链表的某个连续区间上进行操作，例如求最长或最短子字符串、长度最小子数组等。利用循环控制窗口的终止位置，动态移动窗口的起始位置，根据窗口内数据的特征来判断和更新结果。
二分查找：在有序数组中查找目标元素时，可以使用左右两个指针，通过比较中间元素和目标元素的大小，来缩小查找范围，直到找到目标元素或确定其不存在。

283. 移动零【简单】

https://leetcode.cn/problems/move-zeroes/description/?envType=study-plan-v2&envId=top-100-liked

双指针法的核心思想

指针定义:
- lastNonZeroIndex: 这个指针用于跟踪下一个非零元素应放置的位置。
- i: 这个指针用于遍历整个数组。
过程:
- 使用 i 指针遍历数组，检查每个元素。
- 当找到非零元素时，将其移动到 lastNonZeroIndex 指向的位置，并更新 lastNonZeroIndex。
- 在遍历完成后，使用 lastNonZeroIndex 填充剩下的位置为零。

详细步骤

以下是对双指针法在 moveZeroes 方法中的具体应用的详细解释：

1. 初始化指针

1	int lastNonZeroIndex = 0;

初始化 lastNonZeroIndex 为 0，表示下一个非零元素应该放置在数组的起始位置。

2. 遍历数组

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

遍历: 使用 i 从 0 到 nums.size() - 1 遍历每个元素。
条件判断:
- 如果当前元素 nums[i] 不是零，执行以下操作：
  - 将 nums[i] 的值赋给 nums[lastNonZeroIndex]，将非零元素移动到前面。
  - 增加 lastNonZeroIndex，为下一个非零元素腾出位置。

3. 填充零

1
2
3

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

从 lastNonZeroIndex 开始，到数组末尾，将所有剩余的位置填充为零。

示例演示

假设输入数组为 [0, 1, 0, 3, 12]：

第一轮循环:
- i = 0: nums[0] 是零，跳过。
- i = 1: nums[1] 是 1，移动到 nums[0]，更新 lastNonZeroIndex 为 1。
- i = 2: nums[2] 是零，跳过。
- i = 3: nums[3] 是 3，移动到 nums[1]，更新 lastNonZeroIndex 为 2。
- i = 4: nums[4] 是 12，移动到 nums[2]，更新 lastNonZeroIndex 为 3。
此时数组变为 [1, 3, 12, 3, 12]，lastNonZeroIndex 为 `3

392. 判断子序列

https://leetcode.cn/problems/is-subsequence/description/?envType=study-plan-v2&envId=top-interview-150

双指针直接秒了，一次过！

class Solution {

public:

	bool isSubsequence(string s, string t) {
	int slowindex = 0;
	for (int i = 0; i < t.length(); i++) {
		if(t[i] == s[slowindex]) {	
			slowindex++;
		}
	}
	
	return slowindex == s.length();
	}
};

5. 最长回文子串【中等】

对我来说，这题还是很有难度的，不过收获很多，由于是在刷双指针法相关的题目，所以拿到这题就在想如何用双指针做，然后，就得到了下面惨不忍睹的代码：

我的代码

class Solution {
public:
    string longestPalindrome(string s) {
        int right_index = s.length() - 1;
        int result_index = 0;
        for(int i = 0 ; i < s.length(); i++) {
            for(; right_index == 0; right_index--){
                if(s[i] == s[right_index]) {
                    if (i == right_index){
                        return s.substr(result_index, i - result_index + 1);
                    }
                    continue;
                }
            }
        }
        return s.substr(result_index, 1);
    }
};

不过这也暴露出我的一下问题：

对 STL 相关容器和算法不熟悉
多层循环逻辑不清晰
代码结构不清晰
总的来说，上面的代码是一坨屎。

中心扩展法

下面，欣赏一下优秀的代码：

class Solution {
public:
    string longestPalindrome(string s) {
        if (s.empty()) return "";
        int start = 0, maxLength = 1;

        for (int i = 0; i < s.length(); i++) {
            // 奇数长度回文
            int len1 = expandAroundCenter(s, i, i);
            // 偶数长度回文
            int len2 = expandAroundCenter(s, i, i + 1);
            int len = max(len1, len2);
            if (len > maxLength) {
                start = i - (len - 1) / 2;
                maxLength = len;
            }
        }
        return s.substr(start, maxLength);
    }

private:
    int expandAroundCenter(const string& s, int left, int right) {
        while (left >= 0 && right < s.length() && s[left] == s[right]) {
            left--;
            right++;
        }
        return right - left - 1; // 返回回文的长度
    }
};

在这题中，双指针主要应用在 expandAroundCenter 函数中，从基准位置向两边扩展，检查满足回文子串的条件。

具体步骤

初始化：
- 检查字符串是否为空，如果为空，直接返回空字符串。
- 初始化 start 和 maxLength，分别表示最长回文子串的起始位置和长度。
遍历字符串：
- 使用一个 for 循环遍历字符串的每个字符，以每个字符和每两个字符之间的空隙为中心，检查回文子串。
检查回文子串：
- 对于每个字符 i，调用 expandAroundCenter 方法两次：
  - 第一次是以 i 为中心，检查奇数长度的回文子串。
  - 第二次是以 i 和 i+1 为中心，检查偶数长度的回文子串。
- 取这两次检查中较长的回文子串长度。
更新最长回文子串：
- 如果当前找到的回文子串长度大于已知的最长回文子串长度，更新 start 和 maxLength。
返回结果：
- 使用 substr 方法从字符串中提取最长回文子串，并返回该子串。