零.参考文章

双指针技术在数组和链表问题中的应用解析-CSDN博客

一.使用情况

双指针即是在有序数组的情况下，我们通过两个指针在遍历的过程中进行标记，对满足条件的进行处理，直至遍历完整个数组。

二.举个例子

2.1小人过河问题：

一个孤岛上有7个人重量54kg，55kg，56kg，57kg，58kg，59kg，70kg。她们需要逃生到安全的地方。现在有足够的救生艇，但是每个救生艇只能坐两个人，而且每个救生艇最大能承受113kg的重量，那她们最少需要多少救生艇才能全部逃生。

#include <iostream>
#include <list>
#include <iterator> // for std::prev, std::next
#include <algorithm> // for std::sort

using namespace std;

int main()
{
    list<int> l{ 54, 70, 56, 59, 57, 58, 55 };
    l.sort(); // 对列表进行排序
    int limitWeight = 113;
    auto itB = l.begin();
    auto itE = prev(l.end()); // 指向最后一个元素
    int num = 0;

    while (itB != itE)
    {
        // 特别处理剩余两个元素的情况
        if (next(itB) == itE)
        {
            int sum = *itB + *itE;
            if (sum > limitWeight)
            {
                num += 2; // 如果两个元素加起来超过限制，则需要两艘船
            }
            else
            {
                num++; // 否则只需要一艘船
            }
            break; // 处理完后退出循环
        }

        int sum = *itB + *itE;
        if (sum > limitWeight) // 大于限制重量，让itE单独坐船
        {
            num++;
            --itE;
        }
        else // 小于或等于限制重量，两人一起坐船
        {
            num++;
            ++itB;
            --itE;
        }
    }

    // 如果还剩下一个元素（即itB == itE），则需要再加一艘船
    if (itB == itE)
    {
        num++;
    }

    cout << "num = " << num << endl;
    return 0;
}

2.2两数之和等于target

#include <iostream>
#include <list>
#include <iterator> // for std::prev

using namespace std;

int main()
{
    int target = 9;
    list<int> l{ 2, 3, 4, 6, 8 };
    l.sort(); // 确保列表是排序的，因为双指针法要求输入是有序的
    auto itB = l.begin(); // 迭代器指向列表的第一个元素
    auto itE = prev(l.end()); // 迭代器指向列表的最后一个元素
    list<int> returnlist{};

    while (itB != itE)
    {
        int sum = *itB + *itE;
        if (sum > target) // 大于去大
        {
            --itE;
        }
        else if (sum < target) // 小于去小
        {
            ++itB;
        }
        else // 找到了
        {
            returnlist.push_back(*itB);
            returnlist.push_back(*itE);
            break;
        }
    }

    if (!returnlist.empty())
    {
        cout << "Found numbers: [";
        bool first = true;
        for (int num : returnlist)
        {
            if (!first) cout << ", ";
            cout << num;
            first = false;
        }
        cout << "]" << endl;
    }
    else
    {
        cout << "No pair found that adds up to " << target << "." << endl;
    }

    return 0;
}

输出结果