双指针的实践

一、原理

双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或者相反方向（对撞指针）的指针进行扫描，从而达到相应的目的。换言之，双指针法充分使用了数组有序这一特征，从而在某些情况下能够简化一些运算。

伪代码

 void find(int[] list) {
    int left = 0;
    int right = list.length - 1;

    //遍历数组
    while (left <= right) {
        left++;
        // 一些条件判断 和处理
        ... ...
            right--;
    }
}

​ 二、剑指 Offer 48. 最长不含重复字符的子字符串
 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ans = 0;
        int i = -1;
        unordered_map<char, int> hashmap;
        for (int j = 0; j < s.length(); j++) {
            if (hashmap.count(s[j])) { // 字符已经存在
                i = max(i, hashmap[s[j]]); // 更新左指针
            }
            hashmap[s[j]] = j;
            ans = max(ans, j - i); // 计算左指针与右指针的间隔
        }
        return ans;

    }
};

三、反转字符串

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n = s.size();
        for (int left = 0, right = n - 1; left < right; ++left, --right) {
            swap(s[left], s[right]);
        }
    }
};

参考：

双指针算法基本原理和实践 - huansky - 博客园

力扣