基础算法详解：双指针技巧（滑动窗口与快慢指针）

基础算法详解：双指针技巧（滑动窗口与快慢指针）

引用

CSDN

1.

https://blog.csdn.net/U2396573637/article/details/142673132

双指针技巧是C++编程中的一个常用且强大的方法，特别是在处理数组或链表问题时。这种技巧通常有两种主要形态：滑动窗口和快慢指针。接下来，我将详细讲解这两种方法，包括基本原理、使用场景以及代码示例。

滑动窗口（Sliding Window）

滑动窗口可以用来解决一系列数组或字符串问题，尤其是当需要处理“连续”子数组/子字符串时特别有用。其基本思想是使用两个指针（或索引）来表示一个窗口的起始和结束位置，通过移动这些指针来逐步扩展或收缩窗口。

基本思路

• 使用两个指针（left和right），left表示窗口的开始位置，right表示窗口的结束位置。
• 增加right拓展窗口，直到满足某个条件。
• 一旦满足条件，就尝试移动left来收缩窗口，直到条件不再满足。

使用场景

• 查找最长或最短的连续子数组/子字符串。
• 字符串的无重复字符子串问题。

代码示例

以下是寻找给定字符串中，最长无重复字符子串的代码示例：

#include <iostream>
#include <unordered_set>
#include <string>
using namespace std;

int lengthOfLongestSubstring(std::string s) {
    unordered_set<char> charSet;
    int left = 0, maxLength = 0;
    for (int right = 0; right < s.length(); right++) {
        while (charSet.find(s[right]) != charSet.end()) {
            charSet.erase(s[left]);
            left++;
        }
        charSet.insert(s[right]);
        maxLength = max(maxLength, right - left + 1);
    }
    return maxLength;
}

int main() {
    string s = "abcabcbb";
    cout << "Longest substring without repeating characters: ";
    cout << lengthOfLongestSubstring(s) << std::endl;
    return 0;
}

快慢指针（Fast and Slow Pointers）

快慢指针技巧通常用于链表和数组中，其基本概念是使用两个指针以不同的速度遍历结构。

基本思路

• 一个指针（慢指针）每次向前移动一步，另一个指针（快指针）每次向前移动两步。
• 这种方式使得快指针走得比慢指针快，从而可以检测到特定条件（如环的存在）。

使用场景

• 检测链表是否有环。
• 寻找链表的中间节点。

代码示例

以下是检测链表是否有环的代码示例：

#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

bool hasCycle(ListNode *head) {
    if (!head) return false;
    ListNode *slow = head;
    ListNode *fast = head;
    while (fast && fast->next) {
        slow = slow->next;         // 慢指针走一步
        fast = fast->next->next;   // 快指针走两步
        
        if (slow == fast) {
            return true;           // 如果相遇，说明有环
        }
    }
    return false;                  // 遍历完没有相遇，说明没有环
}

int main() {
    ListNode *head = new ListNode(3);
    head->next = new ListNode(2);
    head->next->next = new ListNode(0);
    head->next->next->next = new ListNode(-4);
    head->next->next->next->next = head->next; // 创建环
    if (hasCycle(head)) {
        cout << "List has a cycle." << endl;
    } else {
        cout << "List does not have a cycle." << endl;
    }
    return 0;
}

总结/其他场景

双指针技术是一种高效且灵活的算法策略，对于多种问题都可以应用。在使用双指针时，理解问题的结构及条件是至关重要的。熟练掌握滑动窗口和快慢指针后，可以解决很多典型算法问题。

运用双指针的其它场景：

1. 有序数组的两数之和：在有序数组中找到两个数，使它们的和等于目标值。
2. 反转字符串：使用双指针可以有效地反转一个字符串。
3. 寻找回文串：通过两个指针从两端向中间移动，判断字符串是否回文。
4. 合并两个有序数组：使用两个指针分别指向两个数组的起始位置，进行合并。

算法真题实训

开胃菜：移动零

题目：给定一个数组nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意，必须在不复制数组的情况下原地对数组进行操作。

在这道题中，我们需要将所有的零全部移动到数组末尾不能改变原来非零元素的相对位置。一开始我们的思路可以暴力一些，直接就是两层循环，实现复杂度为O(n²)的代码。不过考虑到数据范围：

• 1 <= nums.length <= 104
• -2^31 <= nums[i] <= 2^31 - 1
  这样做就很容易就超时了，不太保险。那么我们必须想办法优化一下。那么我们就可以使用双指针的思想，定义两个变量记录位置。一个表示零定位指针pre，一个表示非零定位指针cur。

通过循环将零定位指针pre移动到第一个零元素位置，非零定位指针cur移动到pre后面的第一个非零元素位置。交换两个指针的值。

class Solution {
public:
    void moveZeroes(vector<int>& v) {
        int n = v.size();
        int pre = 0, cur = 0;//两个指针同时出发
        while (cur < n) {
            swap(v[pre], v[cur]);
            while (pre < n && v[pre])
                pre++; // 如果前面不为0，前面往后走。
            while (cur < n && !v[cur])
                cur++; // 如果后面为0，后面往后走。
            if (pre > cur)
                swap(pre, cur);
        }
    }
};

class Solution {
public:
    void moveZeroes(vector<int>& v) {
        int n=v.size();
        int pre = 0, cur = 1;//两个指针一前一后
        while (cur<n) {
            if (!v[pre] && v[cur]) swap(v[pre], v[cur]);//如果前面为0，后面不为零，交换
            while (pre<n&&v[pre])pre++;//如果前面不为0，前面往后走。
            while (cur<n&&!v[cur])cur++;//如果后面为0，后面往后走。
            if (pre > cur)swap(pre, cur);
        }
    }
};

进阶篇：有效三角形的个数

题目：给定一个包含非负整数的数组nums，返回其中可以组成三角形三条边的三元组个数。

同样的，我们可以使用三个指针来循环遍历所有的三元组看是否能构成三角形。进行简单的修改后我们才能通过，只是复杂度会很高。

class Solution {
public:
    int triangleNumber(vector<int>& v) {
        sort(v.begin(), v.end());//先进行排序
        int sum = 0;
        int fst = 0;
        for (auto e : v) {
            if (e == 0)fst++;
            else break;
        }//跳过所有的0元素
        for (int i = fst; i < v.size()-2; i++) {//第一条边，从第一个非零元素开始到最后。
            for (int j = i + 1; j < v.size()-1; j++) {//第二条边，从第一条边的下一个元素开始
                int max = v[j] + v[i];//两边之和
                int min = v[j] - v[i];//两边之差
                int p = 0, q = 0;
                for (int k = j + 1; k < v.size(); k++) {//第三条边从第二条边下一个元素开始
                    if (!p && v[k] > min)p = k;
                    //如果q还没找到合适的位置，那么这时候只要第三边大于两边之差即可确定范围上限
                    if (!q && v[k] >= max)q = k;
                    //如果p还没找到合适的位置，那么这时候只要第三边大于两边之和，就不再能确定三角形了
                    if (p && q) break;
                    //如果两个范围都找到了，提前结束循环。
                }
                if (p&&!q)q = v.size();
                //如果正常结束循环，没有进行break，q就没有被赋值，那么q=v.size()；
                sum += (q - p);
                //q、p两个下标位置之间的都可以作为第一、二边的第三边。计入总数。
            }
        }
        return sum;//返回总数。
    }
};

能跑过，但这需要你考虑很多小的细节，还有那么一点可能跑不过测试。我们在算法比赛中不能冒险，所以我们需要其它的方法确保万无一失。什么方法呢？双指针！ 双指针是两个指针，我们要找三个元素的关系，怎么办呢？我们可以选择将一个边用来循环，另外两条边进行双指针化解答。

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        int n=v.size(); 
        sort(nums.begin(), nums.end());
        int sum = 0;
        for (int i = n - 1; i >= 2; i--) {
            int pre = 0, cur = i - 1;
            while (pre < cur) {
                if (nums[pre] + nums[cur] > nums[i]) {
![](https://wy-static.wenxiaobai.com/chat-rag-image/14916007490517631189)
                    sum += (cur - pre);
                    cur--;
                } 
                else pre++;
            }
        }
        return sum;
    }
};