顾名思义，双指针就是用两个指针来解决数组或者列表的问题，常用于查找满足特定条件的数对或元素。

【leetcode167】求两数之和等于target的下标组

思路与分析：先确定下一个数字 i ,然后遍历数组中其他数字，找到 target-i 就算完成任务。我们考虑到这个算法要实现至少要需要双层循环，时间复杂度有点高。在数组中找指定元素【target-i】可以用二分查找呀，时间可以减少很多，那前提就需要先对数组进行排序。虽然这种方法还是用了循环，但也是一种优化呀。

补充一下：二分查找的代码

 while (low <= high) {
                int mid = (high + low) / 2 ;
                if (numbers[mid] == (target - numbers[i]) ){
                    return {i , mid };
                } else if (numbers[mid] > (target - numbers[i])) {
                    high = mid - 1;
                } else {
                    low = mid + 1;

                }

完整代码如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        for (int i = 0; i < numbers.size(); ++i) {
            int low = i + 1, high = numbers.size() - 1;
            while (low <= high) {
                int mid = (high + low) / 2 ;
                if (numbers[mid] == (target - numbers[i])) {
                    return {i, mid};
                } else if (numbers[mid] > (target - numbers[i])) {
                    high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
        }
        return {-1, -1};
    }
};

But 这样时间复杂度还是挺高的，下面用双指针算法解决一下。我们已经将数组排好序了(由小到大)，用两个指针 f 和 e 分别指向第一个元素和最后一个元素，看这两个元素的和与 target 的区别，若和比target 大，那么需要让和变小一点，即 e 左移一个；若和比target 小，那么需要让和变大一点，即 f 右移一个...比较--移动--比较--移动...直到找到和等于 target 的元素即可，但不能一直移动吧，得有个范围限定，必须保证 f 一直在 e 的左边才行。若超出这个范围还没找到 target 那就说明米有答案。

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int f = 0, e = numbers.size() - 1;
        while (f < e) {
            int sum = numbers[f] + numbers[e];
            if (sum == target) {
                return {f, e};
            } else if (sum < target) {
                f++;
            } else {
                e--;
            }
        }
        return {-1, -1};
    }
};

【leetcode 15】三数之和

一个整数数组中找一个三元组[nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

思路与分析：一般看到这样的题目暴力求解，三层for循环，耗时间。后面还需要用哈希表得到不包含重复三元组的最终答案，耗空间。如果数组的规模不大还阔以，但有更好的方法我们会选择更好的方法进行优化。

不重复要求：还是从上个题的二分查找思路开始，（双指针没法指向三个元素），把数组排好序。并且确保 （nums[i]， nums[j] ，nums[k]）的唯一性，那么在实际操作时，找到一组答案之后，要枚举元素 的选取条件就是跟上一次枚举的不一样才阔以。

时间复杂度减少要求：注意，找三个数跟找两个数一样。找到一组数{ nums[j] 、 nums[k]}，满足 nums[j] + nums[k] = -nums[i]，就是双指针问题呀，三层循环就变成了双层循环。

算法部分：

#include <iostream> 
#include <vector>
#include <algorithm> // 用于排序
using namespace std;

class Solution {
public:
    vector<vector<int>> threesum(vector<int>& nums) {
        int n = nums.size(); // 获取数组长度
        sort(nums.begin(), nums.end()); // 对数组进行排序
        vector<vector<int>> result; // 用于存储结果的三元组

        // 外层循环，固定第一个数 nums[i]
        for (int i = 0; i < n; i++) {
            // 跳过重复的第一个数，避免重复解
            if (i > 0 && nums[i] == nums[i - 1]) continue;

            int target = -nums[i]; // 将三数之和问题转化为两数之和问题
            int j = i + 1; // 左指针，指向第二个数
            int k = n - 1; // 右指针，指向第三个数

            // 双指针法，在 [j, k] 范围内寻找两数之和等于 target
            while (j < k) {
                int sum = nums[j] + nums[k]; // 计算当前两数之和

                if (sum < target) {
                    j++; // 如果和小于 target，左指针右移，增大和
                } else if (sum > target) {
                    k--; // 如果和大于 target，右指针左移，减小和
                } else {
                    // 找到符合条件的三元组，加入结果
                    result.push_back({nums[i], nums[j], nums[k]});

                    // 跳过重复的第二个数
                    while (j < k && nums[j] == nums[j + 1]) j++;
                    // 跳过重复的第三个数
                    while (j < k && nums[k] == nums[k - 1]) k--;

                    // 移动指针，继续寻找下一个可能的解
                    j++;
                    k--;
                }
            }
        }

        return result; // 返回结果
    }
};
int main(){
	
	vector<int>nums = {-1, 0, 1, 2, -1, -4};
	Solution solution; 
	vector<vector<int>> result = solution.threesum(nums);
	for(const vector<int>& triplet:result){//const 表示只读 ,triplet 表示一个三元组向量 
		for(int num:triplet){//num表示 三元组中的每一个数字 
			cout<<num<<" ";
		}
		cout<<endl;
	}
	
	return 0;
}

【leetcode11】盛水最多的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

思路与分析：容水量=两指针中较小的那个值*指针间距 现在上边垂线的值是 

[1, 8, 6, 2, 5, 4, 8, 3, 7]  ，两个指针 i 和 j 分别指向1和7。下面应该考虑是移动哪个指针了，若移动大的那个，即 j 指向3，则容水量一定小于移动指针之前（指向7）的状态，因为min不可能比1还大了，而指针间距又在减小，所以容水量是变少了。so，我们应该移动指针小的那个，每次都应该移动小的那个，有三种可能性，移动后水量变少、不变、增多。这时候就应该比较后，更新最大值，并记下位置。

算法与实现：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    vector<int> num = {1, 8, 6, 2, 5, 4, 8, 3, 7};
    vector<int>::iterator i = num.begin(); // 左指针
    vector<int>::iterator j = num.end() - 1; // 右指针，指向最后一个元素
    int max_re = 0; // 初始化最大面积

    while (i < j) {
        // 计算当前面积
        int current_area = min(*i, *j) * (j - i);
        // 更新最大面积
        max_re = max(max_re, current_area);

        // 移动高度较小的指针
        if (*i < *j)  i++;
        else j--;

    }

    cout << max_re << endl; // 输出结果
    return 0;
}