双指针-左右指针-育师

注意：这里的双指针指的不是C和C++的原生指针（指针数据类型），你可以把这里的指针理解为数组下标，这会帮助你更好地理解本文

概念

左右指针，听名字就知道是两个指针，一个在左，一个在右。左右指针特别适用于处理数组和字符串问题。和快慢指针不同，左右指针同时从两边向中间移动，形成对称扫描。

二分法，二分查找是对左右指针最直接的运用（起码看上去比较像）

初始状态->左指针为 0 ，右指针为 n - 1

终止条件->左指针大于右指针

基础模板

int l = 0 , r = n - 1; while(l < n){ if(){ //当左边满足条件 l++; } if(){ //当右边满足条件 r--; } }

例题

两数之和

167. 两数之和 II - 输入有序数组https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted/这是来自力扣的一道题目

题目：给定一个已按非降序的整数数组，请你从数组中找出两个数，让它们的和等于目标数target，假设每个输入有且只有一个解，且不能重复使用相同的元素（注意：这题的下标从 1 开始）

暴力写法

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { for(int i = 1 ; i < numbers.lenght() ; i++){ for(int j = i + 1 ; j <= numbers.lenght() ; j++){ if(numbers[i] + numbers[j] == target){ return {i + 1 , j + 1}; } } } return {-1 , -1}; } };

但是很明显，如果你使用暴力的话，复杂度就来到了O()，想都不用想，包超时的

左右指针写法

利用给定数组非降序的特性，我们可以确定左右指针移动的条件：当左右两数和大于 target 时，左指针向右移动；当左右两束小于 target 时，右指针向左移。

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

通过双指针，我们就成功地将复杂度降到O(n)了

反转字符串

P5705 【深基2.例7】数字反转

题目描述：输入一个不小于 100 且小于 1000，同时包括小数点后一位的一个浮点数，例如 123.4 ，要求把这个数字翻转过来，变成 4.321 并输出。

输入
123.4

输出
4.321

这道题其实不用双指针也行，因为这道题其实用纯语法知识也可以做

常规写法

#include<iostream> using namespace std; int main(){ float n; cin>>n; int ge,shi,bai,xiao; bai=(int)(n)/100; shi=(int)(n)/10%10; ge=(int)(n)%10; xiao=(int)(n*10)%10; cout<<(float)(xiao+ge/10.0+shi/100.0+bai/1000.0); return 0; }

左右指针写法

#include<iostream> using namespace std; int main(){ string temp; cin >> temp; int l = 0 , r = temp.length() - 1; while(l < r){ char t = temp[l]; temp[l] = temp[r]; temp[r] = t; l++; r--; } cout << temp << endl; return 0; }

这题用左右指针真有点莫名其妙了，其实可以用 swap 函数直接交换，不需要 l 和 r 这两个变量