【算法/学习】双指针

✨ 少年要迎着朝阳，活得肆无忌惮 🌏

📃个人主页：island1314

🔥个人专栏：算法学习

🚀 欢迎关注：👍点赞 👂🏽留言 😍收藏 💞 💞 💞

引言：

双指针（Two Pointers）：指的是在遍历元素的过程中，不是使用单个指针进行访问，而是使用两个指针进行访问，从而达到相应的目的。如果两个指针方向相反，则称为「对撞指针」。如果两个指针方向相同，则称为「快慢指针」。如果两个指针分别属于不同的数组 / 链表，则称为「分离双指针」。

在数组的区间问题上，暴力算法的时间复杂度往往是O(n^2)。而双指针利用了区间「单调性」的性质，可以将时间复杂度降到 O(n)。

指针一般情况下将分为三种类类型，分别是：

类型	特点
快慢指针	两个指针步长不同，一般情况下，快的走两步，慢的走一步
对撞指针	两个指针分别指向头尾，并往中间移动，步长不确定，一般为1
区间指针	一般为滑动窗口，两个指针及其间距视作整体，窗口有定长有变长，每次操作窗口整体向右滑动

不管是哪一种双指针，只考虑双指针部分的话，由于最多还是会遍历整个数组一次，因此时间复杂度取决于步长，如果步长是 1，2 这种常数的话，那么时间复杂度就是 O(N)，如果步长是和数据规模有关（比如二分法），其时间复杂度就是 O(logN)。并且由于不管规模多大，我们都只需要最多两个指针，因此空间复杂度是 O(1)。下面我们就来看看双指针的常见套路有哪些。

1. 对撞指针（相向双指针）

1.1 基本概念

对撞指针 ：指的是两个指针 left 、 right 分别指向序列第一个元素和最后一个元素，然后 left 指针不断递增， right 不断递减，直到两个指针的值相撞（即 left == right ），或者满足其他要求的特殊条件为止。对撞指针一般用于顺序结构中，也称为左右端点指针。

求解步骤：

对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼近。
对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：

(1) left == right（两个指针指向同一个位置）

(2) left > right（两个指针错开）

1.2 伪码框架

left, right = 0, len(nums) - 1while left < right:if 满足要求的特殊条件:return 符合条件的值 elif 一定条件 1:left += 1elif 一定条件 2:right -= 1return 没找到 或 找到对应值

1.3 适用范围

对撞指针一般用来解决有序数组或者字符串问题：

查找有序数组中满足某些约束条件的一组元素问题：比如二分查找、数字之和等问题。
字符串反转问题：反转字符串、回文数、颠倒二进制等问题。

1.4 典型例题

🍎二分

二分法的使用条件：
二分法是适用于解决具有“二段性”(单调性)的问题的方法，通常表现为求解满足某一条件的最大值或者最小值

上下界确定。我们可以通过上下界的折半来优化查找。
二段性：对某一范围内的数据，存在一个临界点，使得临界点某一侧的所有数据都满足某一性质，另一侧的所有数据都不满足这一性质，就称这一范围内的数据具有二段性。

二段性包括单调性，即区间内有序，这样二分出来的结果是严格大于或者小于或等于target的。
但是，二段性也体现在非单调性上，也称为局部有序，可以参考 162. 寻找峰值和 33. 搜索旋转排序数组。由这些题我们可以得知，二分法的奥义（本质）不在于单调性，而是二段性。也就是我们能对整体无序但局部有序的序列进行二分法。

下面列出了四种不同类型的目标：

有序数组的二分查找分为这四种类型，这四种实际上是可以相互转换的，但为了方便，一般都转换成类型一的 lower bound 形式，即 ≥ target以及它的变体。

注意：下面下标从0开始，以1为单位，即是在数组中都是整数时可以用的。

nums = [1, 1, 2, 2 ,3 ,3 ,4, 4, 5]
target = 3

35. 搜索插入位置 - 力扣（LeetCode）

思路：

典型双指针二分问题，详情直接看下面代码

AC代码如下

class Solution {
public:int searchInsert(vector<int>& nums, int target) {// 方法1： 闭区间 [left, right]int l = 0, r = nums.size() - 1; while (l <= r) //区间不为空{ int mid = ((r - l) >> 1) + l;if (nums[mid] < target)l = mid + 1;  //范围缩小到[mid + 1, right]elser = mid - 1;  //范围缩小到[left, mid - 1]}return l; // 或者 return r + 1// 方法2：左闭右开区间 [left, right)int l = 0, r = nums.size();while (l < r) //区间不为空{int mid = ((r - l) >> 1) + l;if (nums[mid] < target)l = mid + 1;  //范围缩小到[mid + 1, right)elser = mid;  //范围缩小到[left, mid)}return l; //或者 return r// 方法3：开区间 (left, right）int l = -1, r = nums.size();while (l + 1 < r) //区间不为空{int mid = ((r - l) >> 1) + l;if (nums[mid] < target)l = mid;  //范围缩小到(mid, right)elser = mid;  //范围缩小到(left, mid)}return r; //或者 return l + 1}
};

有人问，怎么不讲左开右闭模板？

左开右闭这种写法一般是处理最大值的，或者说是 < 和 ≤。但是这两都可以转换成 ≥，所以可以用左闭右开模板来解决。

换句话说，上面讲的这三种二分模板，都只需关注 left right 的初始值，以及二分判定条件的写法，其余的代码都是固定的。

34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）

思路：

可以用到我们上个样例的写法，然后可以直接得到第一个位置，最后一个位置的话再进行调整即可

AC代码如下：

class Solution {
public:// nums[mid] = target 时 仍然往左移动int start_searchInsert(vector<int>& nums, int target) { // 返回大于等于 target 的下标,若有target则返回其第一个下标int l = 0, r = nums.size() - 1;while (l <= r) //区间不为空{int mid = ((r - l) >> 1) + l;if (nums[mid] < target)l = mid + 1;  elser = mid - 1; }return l; //或者 return r + 1}//nums[mid] = target 时 仍然往右移动int right_searchInsert(vector<int>& nums, int target) { // 返回大于 target 的位置，若有target则返回其最后一个下标int l = 0, r = nums.size() - 1;while (l <= r) //区间不为空{int mid = ((r - l) >> 1) + l;if (nums[mid] > target) r = mid - 1;  elsel = mid + 1;  }return r;  //或者 return l - 1}vector<int> searchRange(vector<int>& nums, int target) {int start = start_searchInsert(nums, target);if (start == nums.size() || nums[start] != target)return { -1,-1 };// 获取最后一个位置//方法一：查找插入target + 1的位置，然后 - 1就是我们需要查找元素的最后一个下标int end = start_searchInsert(nums, target + 1) - 1;//方法二：int end = right_searchInsert(nums, target);return { start,end };}
};

🍅有序数组暴力枚举 - N数和问题

已知一组数组和一个目标值target，求不重复的在数组中取N个数的和为target的组合。

一般做这样的题的思路是用双指针，分别指向数组的左右两端，并且，数组需要排好序，从小到大。

因为排序后，左右指针才能有规律的移动，比如：当left+right的值大于target，说明他们两个太大了，需要减小，那么只能通过right左移来减小总体值（为什么不让left左移呢？因为不能重复取，之前取过了，就要移向新的值）；当left+right的值小于target，那么只能通过left右移来增加总体值。

当然，当left+right的值等于target，即为结果

881. 救生艇 - 力扣（LeetCode）

思路：

要使需要的船数尽可能地少，应当使载两人的船尽可能地多。

设 people 的长度为 n。考虑体重最轻的人：

若他不能与体重最重的人同乘一艘船，那么体重最重的人无法与任何人同乘一艘船，此时应单独分配一艘船给体重最重的人。从 people 中去掉体重最重的人后，我们缩小了问题的规模，变成求解剩余 n−1 个人所需的最小船数，将其加一即为原问题的答案。

若他能与体重最重的人同乘一艘船，那么他能与其余任何人同乘一艘船，为了尽可能地利用船的承载重量，选择与体重最重的人同乘一艘船是最优的。从 people 中去掉体重最轻和体重最重的人后，我们缩小了问题的规模，变成求解剩余 n−2 个人所需的最小船数，将其加一即为原问题的答案。

实现：先对 people 排序，然后用两个指针分别指向体重最轻和体重最重的人，按照上述规则来移动指针，并统计答案。

AC代码如下：

class Solution {
public:int numRescueBoats(vector<int>& people, int limit) {sort(people.begin(), people.end());int ans = 0, l = 0, r = people.size() - 1;while (l <= r){if (people[r] + people[l] > limit) r--; //只能坐下最胖的那个else { //胖的和廋的都可以坐下l++;r--;}++ans; //需要船的数量}return ans;}
};

🍈其他暴力枚举

11. 盛最多水的容器 - 力扣（LeetCode）

思路：

设两个指针 left、right 分别指向容器的左右两个端点，此时容器的容积为：

V = (right - left) * min( height[right], height[left])

容器的左边界为 height[left]，右边界为 height[right]。

为了方便叙述，我们假设「左边边界」小于「右边边界」。

如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：

容器的宽度一定变小。
由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会增大。
如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度减小，因此容器的容积一定会变小。

由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以 left++ 跳过这个边界，继续去判断下一个左右边界。

当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到 left 与 right 相遇。期间产生的所有的容积里面的最大值，就是最终答案

AC代码如下：

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ans = 0;while (left < right){ans = max(ans, min(height[left], height[right]) * (right - left));if (height[left] < height[right]){left++;}else {right--;}}return ans;}
};

977. 有序数组的平方

思路：

使用两个指针分别指向位置 0 和 n−1，每次比较两个指针对应的数，选择较大的那个逆序放入答案并移动指针。而且这种方法无需处理某一指针移动至边界的情况，

AC代码如下：

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {int n = nums.size();vector<int> ans(n);int l = 0, r = n - 1;int pos = n - 1; //ans的下标移动，从右往左while (l <= r){if (nums[l] * nums[l] > nums[r] * nums[r]) {ans[pos] = nums[l] * nums[l]; l++;}else {ans[pos] = nums[r] * nums[r];r--;}pos--;}return ans;}
};

2. 快慢指针

2.1 基本概念

快慢指针：又称为龟兔赛跑算法，指的是两个指针从同一侧开始遍历序列，且移动的步长一个快一个慢。移动快的指针被称为「快指针（fast）」，移动慢的指针被称为「慢指针（slow）」。两个指针以不同速度、不同策略移动，直到快指针移动到数组尾端，或者两指针相交，或者满足其他特殊条件时为止。这种方法对于处理「环形」链表或数组非常有用。

本方法需要我们对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一慢。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

求解步骤：

使用两个指针 slow、fast。slow 一般指向序列第一个元素，即：slow = 0，fast 一般指向序列第二个元素，即：fast = 1。
在循环体中将左右指针向右移动。当满足一定条件时，将慢指针右移，即 slow += 1。当满足另外一定条件时（也可能不需要满足条件），将快指针右移，即 fast += 1。
到快指针移动到数组尾端（即 fast == len(nums) - 1），或者两指针相交，或者满足其他特殊条件时跳出循环体。

2.2 伪码框架

slow = 0
fast = 1
while 没有遍历完：if 满足要求的特殊条件:slow += 1fast += 1
return 合适的值

2.3 适用范围

用于处理数组中的移动、删除元素问题
判断一个链表是否存在环。
找到链表的中间节点。
判断链表是否为回文结构。

2.4 典型例题

🥑链表快慢指针

142. 环形链表 II - 力扣（LeetCode）

思路：

找数学规律：当快慢指针在环中相遇，链表的起点到入环点=快慢指针相遇点到入环点的距离。所以相遇之后，定义新的游标在链表起点，此时该游标和慢指针一起以相同步长走，相遇即到了入环点。

图解：

AC代码如下：

class Solution {
public:ListNode* detectCycle(ListNode* head) {int f = 0;ListNode* fast = head, * slow = head;// 1. 判断链表是否有环，fast走两步，slow走一步while (fast && fast->next){fast = fast->next->next;slow = slow->next;if (slow == fast){f = 1;break;}}// 2. 无环时直接返回空节点if (f == 0) return nullptr;// 3.然后找入环点fast = head;while (fast != slow){fast = fast->next;slow = slow->next;}return fast;}
};

🍉数组快慢指针

26. 删除有序数组中的重复项 - 力扣（LeetCode）

思路：

定义两个快慢指针 slow，fast。其中 slow 指向去除重复元素后的数组的末尾位置。fast 指向当前元素。
令 slow 在后， fast 在前。令 slow = 0，fast = 1。
比较 slow 位置上元素值和 fast 位置上元素值是否相等。
如果不相等，则将 slow 后移一位，将 fast 指向位置的元素复制到 slow 位置上。将 fast 右移 1 位。
重复上述步骤，直到 fast 等于数组长度。
返回 slow + 1 即为新数组长度。(防止最后一个元素无法遍历到)

AC代码如下：

class Solution {
public:int removeDuplicates(vector<int>& nums) {if (nums.size() == 0) return 0;int slow = 0, fast = 1; while (fast < nums.size()){if (nums[slow] != nums[fast]) {nums[++slow] = nums[fast];}fast++;}return slow + 1;}};

202. 快乐数 - 力扣（LeetCode）

思路：

先书写一个函数获取该数的平方和，然后定义两个指针slow和fast，slow走一步，fast走两步，判断两个指针相遇的值即可

AC代码如下：

class Solution {
public:int bitSum(int n) // 平方和{int sum = 0;while (n){int t = n % 10;sum += t * t;n /= 10;}return sum;}bool isHappy(int n) {int slow = n, fast = bitSum(n);while (slow != fast){slow = bitSum(slow);fast = bitSum(bitSum(fast));}return slow == 1;}
};

3. 区间类型指针（同向双指针）

3.1 基本概念

滑动：说明这个窗口是移动的，也就是移动是按照一定方向来的。
窗口：窗口大小并不是固定的，可以不断扩容直到满足一定的条件；也可以不断缩小，直到找到一个满足条件的最小窗口；当然也可以是固定大小。

求解步骤：

定义变量：确定需要维护的变量：数之和，最大最小长度，哈希表等
滑动窗口：确定滑动窗口的左右边界，开始滑动窗口
合法更新：在滑动窗口有效的情况下，合法的更新需要维护的变量
非法更新（二次更新）：在滑动窗口无效或者即将无效的情况下，更新维护的变量，并且收缩滑动窗口的左边界，非法更新的两种情况：
滑动窗口的长度是固定的！！！ 使用 if条件来更新
滑动窗口的长度是可变的！！！ 使用 while条件来更新
返回与得到答案

3.2 伪码框架

int func(vector<int>& nums,int k)
{//Step1. 定义维护变量：1. unordered_map<char,int> m;	//在需要统计字符或者数字出现的次数的时候，使用哈希表2. int sum=0,res=0;			//在需要记录整数数组中的子序列和或者其他求和时，使用sum记录每一次滑动窗口的子和，再利用res得到最大的或者最小的结果	3. int len=0,start=0;		//得到字符串的字串，len记录字串长度，start标识字串开始位置//Step2. 确定滑动窗口的边界，开始滑动：int left=0,right=0;while (right< n) 	// n: 数组长度	{//Step3. 合法更新：每进行一次滑动时，必须要更新的变量：如Step1的哈希表，sum,res,len与start等等......if (满足条件) //满足某一种条件：例如滑动窗口的长度：right-left+1 与某个值相等时，则进行一次判断，保存临时结果{//更新：res=max(res,sum)  ......}//Step4: 非法更新//(1): 滑动窗口的长度固定：使用if来更新窗口while (right-left+1 > m.size())//举个例子：无重复字符的最长字串，你的窗口长度大于哈希表的长度，则一定含有重复元素，因此更新左边界，使用if{.....}//(2)： 滑动窗口的长度不固定，使用while来更新窗口	if (right>=k-1)//举个例子：子数组的最大平均值，子数组规定长度不能超过k，因此滑窗长度固定{.....}right++;//此处可以改为for循环}return res;//Step5: 返回结果
}

3.3 适用范围

简而言之，滑动窗口算法在一个特定大小的字符串或数组上进行操作，而不在整个字符串和数组上操作，这样就降低了问题的复杂度，从而也达到降低了循环的嵌套深度。其实这里就可以看出来滑动窗口主要应用在数组和字符串上。

3.4 典型例题

☘️定长滑动窗口

1456. 定长子串中元音的最大数目 - 力扣（LeetCode）

思路：

很典型的定长滑动窗口，我们可以遍历字符串 s 每个长度为 k 的子串，求出其中包含的元音字母个数，并找出最大值。

AC代码如下：

class Solution {
public:bool Is_vowel(char x){if (x == 'a' || x == 'e' || x == 'i' || x == 'o' || x == 'u') return true;return false;}int maxVowels(string s, int k) {int l = 0, r = 0;int res = 0, ans = 0;while (r < s.length()){if (Is_vowel(s[r++])) ans++;while(r - l + 1 > k){if(Is_vowel(s[l++])) ans--;}if (r - l + 1 == k) {res = max(res, ans);}r++;}return res;}
};

DNA序列

思路：

和上题基本大差不差，详情可见代码

AC代码如下：

#include <iostream>
#include <string>
#include <vector>
using namespace std;//DNA序列
void solve3()
{string s;int k;cin >> s >> k;// cnr用来统计CG数目，maxcnt用来统计之前窗口内CG数目最大值，begin记录标记结果的起始位置int maxcnt = 0, cnt = 0, n = s.size(), begin = 0;string t, ret;方法一：暴力//for (int i = 0; i < n; i++)//{//	t = s.substr(i, k);//	cnt = 0;//	for (auto e : t)//	{//		if (e == 'C' || e == 'G') cnt++;//	}//	if (cnt > maxcnt) {//		maxcnt = cnt;//		begin = i;//	}//}//方法二：滑动窗口int l = 0, r = 0;while (r < n){if (s[r] == 'C' || s[r] == 'G') cnt++;while (r - l + 1 > k) //窗口内的总数量超过cnt，出窗口{if (s[l] == 'C' || s[l] == 'G')cnt--;l++;}if (r - l + 1 == k) {if (cnt > maxcnt) {begin = l;maxcnt = cnt;}}r++;}ret = s.substr(begin, k);cout << ret << endl;
}int main() {solve3();
}

🍀变长滑动窗口

1004. 最大连续1的个数 III - 力扣（LeetCode）

思路：

使用 left 和 right 两个指针，分别指向滑动窗口的左右边界。
right 主动右移：right 指针每次移动一步。当 nums[right] 为 0，说明滑动窗口内增加了一个 0；
left 被动右移：判断此时窗口内 0 的个数，如果超过了 K，则 left 指针被迫右移，直至窗口内的 0 的个数小于等于 K 为止。
滑动窗口长度的最大值就是所求。

AC代码如下：

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int res = 0, zeros = 0, l = 0, r = 0;while (r < nums.size()){if (nums[r] == 0) zeros++; //计算窗口内 0 的个数、while (zeros > k) {if (nums[l++] == 0) zeros--;}res = max(res, r - l + 1); // 每个窗口可得到最大数目1都计算一遍++r;}return res;}
};

209. 长度最小的子数组 - 力扣（LeetCode）

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ans = INT_MAX; // 1.  l、r左右指针，sum计算窗口内总和int l = 0, r = 0, sum = 0; while (r < nums.size()) {// 2. 合法更新，窗口滑动一下，把这个数字想加，计算之和sum += nums[r];// 3. //4. 非法更新（二次更新）：当sum满足条件时，试探是否有更好的办法可以实现，即缩小窗口，有没有长度更小的子数组满足>=targetwhile (sum >= target) {ans = min(ans, r - l + 1);sum -= nums[l++];}r++;}return ans == INT_MAX ? 0 : ans;}
};

713. 乘积小于 K 的子数组 - 力扣（LeetCode）

思路：

滑动窗口做法，右边入窗口，若窗口内的值超过k就出窗口，每走一步就需要加上 j - l + 1，对应子数组的数目

注：特判 k=0 和 k=1，这样 while 循环中就无需判断 i <= j 了。

AC代码如下：

class Solution {
public:int numSubarrayProductLessThanK(vector<int>& nums, int k) {if (k <= 1) return 0;int l = 0, r = 0, ans = 0;int prod = 1; //窗口内的总乘积while (r < nums.size()){prod *= nums[r];while (prod >= k){ //出队列prod /= nums[l++];}ans += r - l + 1;r++;}return ans;}
};

4. 其他类型指针

4.1 中心扩展算法

5. 最长回文子串 - 力扣（LeetCode）

思路：

回文中点可能是一个字符或者两个字符，以这为起点，两个左右指针分别扩散切判断是否相等，达到临界条件则存储和比较最大回文串。

AC代码如下：

class Solution {
public:string longestPalindrome(string s) {//中心扩展算法//从每一个位置mid出发，向两边扩散int begin = 0;//记录最长回文子串的起点int maxLen = 0;//记录最长回文子串的长度int len = 1;for (int mid = 0; mid < s.length(); mid++) {int l = mid - 1, r = mid + 1;//向左侧扩展，直到超过边界或遇到与中心字符不等跳出while循环while (l >= 0 && s[l] == s[mid]) {l--;//left字符与mid字符一致，继续左移len++;//与mid字符一致，回文长度+1}//向右侧扩展，直到超过边界或遇到与中心字符不等跳出while循环while (r < s.size() && s[r] == s[mid]) {r++;//right字符与mid字符一致，继续左移len++;//与mid字符一致，回文长度+1}//同时向左右两侧扩展while (l >= 0 && r < s.size() && s[l] == s[r]) {//注意此处，在最后一次循环中，即最长回文子串索引为：i~j，此时的left=i-1，right=j+1l--;r++;len += 2;}if (len > maxLen) {begin = l;maxLen = len;}len = 1; }//返回子串,从pos位开始，长度为lenreturn s.substr(begin + 1, maxLen);}
};

4.2 快慢指针变体

392. 判断子序列 - 力扣（LeetCode）

思路：

从前往后匹配，初始化两个指针 i 和 j，分别指向 s 和 t 的初始位置。每次贪心地匹配，匹配成功则 i 和 j 同时右移，匹配 s 的下一个位置，匹配失败则 j 右移，i 不变，尝试用 t 的下一个字符匹配 s。

AC代码如下：

class Solution {
public:bool isSubsequence(string s, string t) {int i = 0, j = 0;while (i < s.length() && j < t.length()){if (s[i] == t[j]) i++;j++;}return i == s.size();}
};

4.3 从尾到头逆序

88. 合并两个有序数组 - 力扣（LeetCode）

思路：

使用双指针方法。每次从两个数组中取出较大的值插入num1中，从后往前插入

AC代码如下：

class Solution {
public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {int p1 = m - 1, p2 = n - 1, k = m + n - 1; while (p1 >= 0 || p2 >= 0) //从后往前插{if (p2 < 0 || (p1 >= 0 && nums1[p1] >= nums2[p2])) // 当p2 < 0 时说明num2已经遍历完毕，只用遍历nums1即可nums1[k--] = nums1[p1--];else nums2[k--] = nums2[p2--];}}
};