双指针算法通过两个变量或下标遍历数据，常用于数组和链表场景。本文介绍其原理及在排序数组中的应用，通过两数之和、三数之和、四数之和案例演示如何降低时间复杂度。代码示例涵盖 C++ 实现，包含去重逻辑与边界处理。
在本文会为大家带来算法中有关双指针的讲解。
什么是双指针？
从字面上来看是不是就是利用两个指针来进行题目的解答？但是首先我们要明确的一点是虽然这个算法的名称叫做双指针，但还是其在实际操作的时候并不一定是实例化出两个指针在进行操作，有可能是数组的下标，又或者是根据我们的想象定义出来的两个变量。所以这里的'指针'实际是非常灵活的，本质是一种变量，可以是指针，也可以是数组下标。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online
双指针有什么优点？
既然双指针本质上是一种变量，无非数量为两个罢了，为啥会被列入算法之中？笔者认为重要的通过这个双指针能够帮助我们简化一些冗余的步骤，从而提高算法效率。对于双指针这个算法，往往应用于一个封闭，固定的场景，比如数组，链表等，一般而言其长度是不会变化的。因此在这种场景下，当我们为了去满足需求时，往往会考虑暴力求解的方法，因为在这个场景下，所有的可能性是唯一的，我们只需要嵌套多层嵌套去穷举，与所求进行比对便可以拿到我们想要的结果。
但是当穷举数据过多，未免时间复杂度就会过大，这时候通过双指针的方法我们就能够将其中一些不必要的穷举省去，达到降低复杂度的效果。原本为 O(N) 的穷举，可能只需要 O(1) 就可以解决，即降低一层。
那么在实际应用中，我们到底是如何通过双指针来达到降低时间复杂度的效果呢？下面我们就来通过几个案例来看看。
注：以下题目的解法相比于暴力穷举，双指针可能并不是唯一的优化算法，但是限于本文，于是采取双指针的解法。
对于这个题目，我们要知道这个题目的要求是要在给定数组中找到两个下标不同的元素，其之和为给定数字，并将其元素值进行返回。
首先，当我们拿到这道题目的时候第一个想到的就是暴力穷举法，通过两层循环，来判断是否与 target 相等，时间复杂度为 O(N²)。
但是要怎么优化呢，就可以通过双指针的方法。第一，我们会发现这个数组是固定长度；其次在进行双指针之前，我们需要先对数组进行一个升序的排序（降序也可以），排序之后，我们就会发现其实有些穷举是没有必要的。我们以排完序的数组为例：2,5,8,15,16，在这之中我们想找和为 7 的两个数字，当我们将 2 和 5 加起来等于 7 的时候，对于后面的数字的其实我们就无需考虑了，因为这是一个升序的数组，后面的数字之和一定会比 2 和 5 加起来大，这也是我们优化的地点。
那么代码具体是如何实现呢：
图示如下：
找到了
没找到
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int left = 0;
int right = nums.size() - 1;
while (left < right) {
int sum = nums[left] + nums[right];
if (sum == target) {
return {nums[left], nums[right]};
} else if (sum < target) {
left++;
} else {
right--;
}
}
return {};
}
};
本题目的要求是我们要在指定数组中找到三个元素和为 0 的元素组，且返回的三元组不得重复，像【0,2，-2】和【2,0，-2】就只能返回其一。
本题采取暴力穷举需要三重循环，即时间复杂度为 O（N³），但是用双指针的方法可降至 O(N²)。
实现思路：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ret;
for (int i = 0; i < nums.size(); ++i) {
// 对 nums[i] 去重
if (i > 0 && nums[i] == nums[i - 1]) continue;
// 找和为 -nums[i] 的
if (nums[i] > 0) break;
int left = i + 1;
int right = nums.size() - 1;
while (left < right) {
if (nums[left] + nums[right] == -nums[i]) {
ret.push_back({nums[i], nums[left], nums[right]});
right--;
// 对 num[right] 去重
while (nums[right] == nums[right + 1]) {
right--;
if (left > right) break;
}
} else if (nums[left] + nums[right] > -nums[i]) {
right--;
} else {
left++;
}
}
}
return ret;
}
};
本题与上一题类似，只不过由三个数变成四个数。
本题采取暴力穷举需要四重循环，即时间复杂度为 O（N^4），但是用双指针的方法可降至 O(N^3)。
实现思路：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> ret;
sort(nums.begin(), nums.end());
size_t sz = nums.size();
// 解决溢出问题 long long
for (size_t i = 0; i < sz;) {
// 转变求三数和
for (int j = i + 1; j < sz;) {
// 转变为求两数和
long long target1 = (long long)target - nums[i] - nums[j];
int left = j + 1;
int right = sz - 1;
while (left < right) {
if (nums[left] + nums[right] == target1) {
ret.push_back({nums[i], nums[j], nums[left], nums[right]});
right--;
// 对 num[right] 去重
while (nums[right] == nums[right + 1]) {
right--;
if (left > right) break;
}
} else if (nums[left] + nums[right] > target1) {
right--;
} else {
left++;
}
}
j++;
while (j < sz && nums[j] == nums[j - 1]) j++;
}
i++;
while (i < sz && nums[i] == nums[i - 1]) i++;
}
return ret;
}
};
到此为止，对于双指针的讲解已完成一部分，下一部分我们将在下一节继续讲解。