双指针是一种解决问题的技巧或者思维方式，指在访问一个序列中的数据时使用两个指针进行扫描，两个指针可以是同向的，也可以是反向的；我们的关注点可以是这两个指针指向的两个元素本身，也可以是两个指针中间的区域。
左右指针
01、左右指针的概念
左右指针是初始将两个指针分别放在头和尾的位置，然后相向开始移动，直到两个指针相遇；左右指针一般用在有序数组中，可以批量的排除不符合要求的元素，将两重循环O(n2)的时间复杂度转化为一重循环O(n+m)的线性复杂度。
02、应用示例-二分查找
二分查找就是利用有序的特点，一次可以排除一半数据。
//nums中查找等于target的元素的下标
int searchInsert(vector<int>& nums, int target)
{
int left = 0;
int right = nums.size()-1;
while(left <= right)
{
int mid = left + (right-left)/2;
if( nums[mid] > target )//mid处的元素值比target大，则区间[mid,right]中的元素都比target大
{
right = mid-1;//缩小右边界，排除一半数据
}
else if( nums[mid] < target )//mid处的元素值比target小，则区间[left,mid]中的元素都比target小
{
left = mid +1;//扩大左边界，排除一半数据
}
else
{
resault = mid;//找到等于target 的元素了
}
}
return -1;
}
Code language: JavaScript (javascript)03、应用示例-两数之和Ⅱ-输入有序数组
给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1
必须小于 index2。说明: 返回的下标值（index1 和
index2）不是从零开始的。你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。示例: 输入: numbers = [2, 7, 11,
15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
力扣（LeetCode）第167题
常规暴力解法也是使用双指针，先固定一个指针 left，然后另一个指针 right 开始遍历，若没有找到，则移动 left ，然后再次用 right
进行遍历。
利用数组已经有序的特点，可以参考二分查找的思想，批量的进行排除数据。开始将 left 、right 分别放在数组的两端，比较 nums[left] +
nums[right]：
若 nums[left] + nums[right] > target ,因为nums[left] 已经是最小值，则 right 和 [left,right-1] 中的元素组合都可以排除；需要缩小right
若 nums[left] + nums[right] < target ,因为nums[right] 已经是最大值，则 left 和 [left+1,right] 中的元素的组合都可以排除；需要增大left
class Solution {
public:
vector twoSum(vector& numbers, int target) {
int left = 0, right = numbers.size() - 1;//初始化left和right指针
while (left < right)
{
int sum = numbers[left] + numbers[right];
if (sum == target)
return {left + 1, right + 1};
else if (sum < target)//比target小，则需要增大较小的数
left++;
else//比target大，则需要缩小较大的数
right--;
}
return {-1, -1};
}
};
Code language: PHP (php)
声明：本站稿件凡恩品牌资讯以外部分类目资讯转载来自于互联网，如有疑义请联系我们删除。
