引言

双指针算法是一种在数组或链表中使用两个指针（通常分别指向数组的两端）来高效解决问题的算法。双指针的技巧主要分为两类：左右指针和快慢指针。左右指针：两个指针相向而行或者相背而行；快慢指针：两个指针同向而行，但是一快一慢。

双指针算法的核心思想

双指针算法通过维护两个指针协同遍历数据结构，将暴力解法的时间复杂度从 O (n²) 优化至 O (n)，核心策略包括：

1. 缩减搜索空间：通过指针移动排除无效区间
2. 利用单调性：基于数据有序性减少重复计算
3. 同步 / 异步移动：根据问题需求设计指针移动逻辑

适用场景特征：

• 线性数据结构（数组、链表、字符串）
• 存在明显的位置关联性（如对称性、区间特性）
• 可分解为两两关系的问题（如两数之和、三数之和）

双指针算法的分类与应用

1. 左右指针（对撞指针）

应用方向：

• 有序数组两数之和
• 盛水最多的容器
• 回文字符串验证

代码模板：

cpp

int left = 0, right = n-1;
while (left < right) {
    if (满足条件) return 结果;
    else if (条件分支1) left++;
    else right--;
}

真题示例（LeetCode 15. 三数之和）：

cpp

vector<vector<int>> threeSum(vector<int>& nums) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int n = nums.size();
    for (int i=0; i<n-2; ++i) {
        if (i>0 && nums[i]==nums[i-1]) continue;
        int left = i+1, right = n-1;
        while (left < right) {
            int sum = nums[i]+nums[left]+nums[right];
            if (sum == 0) {
                res.push_back({nums[i], nums[left], nums[right]});
                while (left<right && nums[left]==nums[left+1]) left++;
                while (left<right && nums[right]==nums[right-1]) right--;
                left++; right--;
            } 
            else if (sum < 0) left++;
            else right--;
        }
    }
    return res;
}

2. 快慢指针

应用方向：

• 链表环检测（Floyd 判圈算法）
• 链表中点定位
• 数组去重 / 元素迁移

代码模板：

cpp

int slow = 0, fast = 0;
while (fast < n) {
    if (满足条件) {
        swap(arr[slow], arr[fast]);
        slow++;
    }
    fast++;
}

真题示例（LeetCode 26. 有序数组去重）：

cpp

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast=1; fast<nums.size(); ++fast) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
        }
    }
    return slow + 1;
}

3. 滑动窗口（同向双指针）

应用方向：

• 最长无重复子串
• 最小覆盖子串
• 区间最大值 / 平均值

代码模板：

cpp

int left = 0, right = 0;
while (right < n) {
    // 增大窗口
    window.addLast(nums[right]);
    right++;
    
    // 缩小窗口
    while (windows needs shrink) {
        window.removeFirst(nums[left]);
        left++;
    }
}

真题示例（LeetCode 3. 最长无重复子串）：

cpp

int lengthOfLongestSubstring(string s) {
    unordered_set<char> window;
    int left=0, max_len=0;
    for(int right=0; right<s.size(); ++right){
        while(window.count(s[right])){
            window.erase(s[left]);
            left++;
        }
        window.insert(s[right]);
        max_len = max(max_len, right-left+1);
    }
    return max_len;
}

4. 分离双指针（多序列处理）

应用方向：

• 合并有序数组
• 判断子序列
• 区间列表交集

真题示例（LeetCode 88. 合并有序数组）：

cpp

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int p1 = m-1, p2 = n-1, p = m+n-1;
    while (p1 >=0 && p2 >=0) {
        nums1[p--] = (nums1[p1] > nums2[p2]) ? nums1[p1--] : nums2[p2--];
    }
    while (p2 >=0) nums1[p--] = nums2[p2--];
}

双指针算法的优化技巧

1. 贪心策略的应用

在盛最多水的容器问题中，我们可以通过贪心策略来优化算法。具体来说，我们可以从数组的两端开始，逐步向中间移动指针，计算每一步的面积，并记录最大面积。

初始状态：左指针 L=0，右指针 R=n-1，获得最大宽度。

移动策略：总是移动高度较小的指针（短板效应），保留较高挡板的潜在价值。

数学证明：设 h [L] < h [R]，若移动右指针：

• 宽度必然减小
• 新高度 ≤ min (h [L], h [R])
• 容积必然减小

2. 滑动窗口的优化

滑动窗口主要用来解决子数组的问题，比如寻找某个条件的最长或者最短的子数组。滑动窗口本质上就是维护一个可变大小的窗口，不断滑动，更新答案。

基于滑动窗口的算法的时间复杂度为 O (N)，左右双指针不会回退，只会增加，每个元素最多完成一次入窗或者出窗的操作。

双指针算法的应用案例

1. 链表问题

1.1 链表环检测

使用快慢指针可以检测链表中是否存在环。快指针每次移动两步，慢指针每次移动一步，如果存在环，快指针最终会追上慢指针。

cpp

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

1.2 链表相交

使用双指针可以找到两个链表相交的节点。两个指针分别从两个链表的头节点开始遍历，当一个指针到达链表末尾时，将其重定向到另一个链表的头节点。如果两个链表相交，这两个指针最终会在相交节点相遇。

cpp

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
    ListNode *p1=headA,*p2=headB;
    if(headA==nullptr||headB==nullptr)return nullptr;
    while(p1!=p2){
        p1=p1==nullptr?headB:p1->next;
        p2=p2==nullptr?headA:p2->next;
    }
    return p1;
}

2. 数组问题

2.1 移动零

使用快慢指针可以将数组中的零移动到数组的末尾，同时保持非零元素的相对顺序。

cpp

void moveZeroes(vector<int>& nums) {
    int slow = 0;
    for (int fast = 0; fast < nums.size(); fast++) {
        if (nums[fast] != 0) {
            swap(nums[slow], nums[fast]);
            slow++;
        }
    }
}

2.2 有序数组的平方

使用双指针可以将有序数组的平方按升序排序。由于数组是有序的，平方后的最大值一定在数组的两端产生，所以我们可以从两端向中间移动指针，比较平方后的大小，将较大的平方值放在排序后的数组的末尾。

cpp

vector<int> sortedSquares(vector<int>& nums) {
    int n = nums.size();
    vector<int> res(n);
    int left = 0, right = n - 1;
    int i = n - 1;
    while (left <= right) {
        if (abs(nums[left]) > abs(nums[right])) {
            res[i] = nums[left] * nums[left];
            left++;
        } else {
            res[i] = nums[right] * nums[right];
            right--;
        }
        i--;
    }
    return res;
}

3. 字符串问题

3.1 验证回文串

使用双指针可以验证一个字符串是否是回文串。左指针从字符串的起始位置开始，右指针从字符串的末尾位置开始，比较两个指针指向的字符是否相等，如果不相等，则字符串不是回文串；如果相等，则移动指针继续比较。

cpp

bool isPalindrome(string s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        while (left < right && !isalnum(s[left])) {
            left++;
        }
        while (left < right && !isalnum(s[right])) {
            right--;
        }
        if (tolower(s[left]) != tolower(s[right])) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

3.2 反转字符串

使用双指针可以反转一个字符串。左指针从字符串的起始位置开始，右指针从字符串的末尾位置开始，交换两个指针指向的字符，然后移动指针继续交换，直到两个指针相遇。

cpp

void reverseString(vector<char>& s) {
    int left = 0, right = s.size() - 1;
    while (left < right) {
        swap(s[left], s[right]);
        left++;
        right--;
    }
}

双指针算法的优化与扩展

1. 并行双指针技术

并行双指针技术是一种高效的并发控制机制，用于在多线程环境中同步访问共享数据。它通过两个指针读指针和写指针来区分不同类型的访问，从而减少锁的竞争和加锁的时间。这种机制能够提高并发性能，适用于高吞吐量的并发场景。

并行双指针技术的核心在于实现一个高效的原子操作，以保证读指针和写指针的同步更新。这种原子操作通常通过特定的硬件指令或软件算法来完成，以确保数据的一致性和完整性。

2. 双指针在流式处理中的应用

在流式处理中，双指针技术可以用于实时监测数据变化，实现数据的动态更新和筛选。双指针技术还可以应用于数据流的去重、去噪等预处理操作，为后续的数据分析提供高质量的数据。

双指针算法在实时数据流处理中的应用优势包括：

• 高效性：双指针算法在处理实时数据流时，通过两个指针的配合，可以在单次遍历中完成查找、排序等操作，显著减少算法的复杂度，提高处理速度。
• 内存优化：与传统算法相比，双指针算法通常只需要常数级别的额外空间，这对于内存资源有限的环境尤为重要，如移动设备和嵌入式系统。
• 实时性：双指针算法适用于处理实时数据流，因为它能够快速响应数据变化，及时处理新到达的数据，满足实时性要求。

3. 双指针在机器学习中的应用

在机器学习中，双指针技术可以用于特征选择和模型优化。例如，在特征选择中，可以使用双指针技术来选择最相关的特征，提高模型的性能和泛化能力。在模型优化中，可以使用双指针技术来优化模型的参数，提高模型的训练效率和预测精度。

结论

双指针算法是一种高效的算法设计技巧，通过维护两个指针协同遍历数据结构，可以将暴力解法的时间复杂度从 O (n²) 优化至 O (n)。双指针算法的核心思想包括缩减搜索空间、利用单调性和同步 / 异步移动。双指针算法的分类包括左右指针、快慢指针、滑动窗口和分离双指针，每种分类都有其特定的应用场景和代码模板。

双指针算法的应用广泛，包括链表问题、数组问题和字符串问题等。在实际应用中，双指针算法可以与贪心策略、滑动窗口等算法结合使用，进一步提高算法的效率和性能。

双指针算法的优化与扩展包括并行双指针技术、双指针在流式处理中的应用和双指针在机器学习中的应用等。这些扩展进一步拓宽了双指针算法的应用领域，提高了双指针算法的实用性和灵活性。

总之，双指针算法是一种非常实用的算法设计技巧，掌握双指针算法对于提高算法设计能力和解决实际问题具有重要意义。