算法-双指针

双指针

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。

双指针三兄弟，快慢指针、双向指针（对撞指针）和滑动窗口；

快慢指针

快慢指针中的快慢指的是移动的步长，即每次向前移动速度的快慢。

常用于归并排序找中点和链表是否有环；

例题：判断链表是否有环

#include <iostream>

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

bool hasCycle(ListNode *head) {
    if (!head || !head->next) {
        return false;
    }
    
    ListNode *slow = head;
    ListNode *fast = head->next;
    
    while (slow != fast) {
        if (!fast || !fast->next) {
            return false;
        }
        slow = slow->next;
        fast = fast->next->next;
    }
    
    return true;
}

双向指针（对撞指针）

双向指针（两个指针一个从最左，一个从最右出发进行查找），典型应用为二分查找。

常用于反正数组；

例题：在有序数组中找到两个数，使它们的和等于目标值

#include <iostream>
#include <vector>

using namespace std;

vector<int> twoSum(vector<int>& nums, int target) {
    int left = 0, right = nums.size() - 1;
    
    while (left < right) {
        int current_sum = nums[left] + nums[right];
        if (current_sum == target) {
            return {left, right};
        } else if (current_sum < target) {
            left++;
        } else {
            right--;
        }
    }
    
    return {-1, -1}; // 如果找不到，返回一个无效的结果
}

滑动窗口

滑动窗口（两个指针一前一后出发，两个指针中间维持一个窗口结构。

常用于子串问题；

例题：找到数组中满足条件的最小连续子数组，使其和大于或等于给定值

#include <iostream>
#include <vector>

using namespace std;

int minSubArrayLen(int s, vector<int>& nums) {
    int n = nums.size();
    int left = 0;
    int min_len = INT_MAX;
    int current_sum = 0;
    
    for (int right = 0; right < n; ++right) {
        current_sum += nums[right];
        
        while (current_sum >= s) {
            min_len = min(min_len, right - left + 1);
            current_sum -= nums[left];
            left++;
        }
    }
    
    return (min_len != INT_MAX) ? min_len : 0;
}