双指针
双指针
常见的双指针有两种形式，一种是对撞指针，一种是左右指针。
对撞指针：一般用于顺序结构中，也称左右指针。
- 对撞指针从两端向中间移动。一个指针从最左端开始，另一个从最右端开始，然后逐渐往中间逼
近。 - 对撞指针的终止条件一般是两个指针相遇或者错开（也可能在循环内部找到结果直接跳出循环），也就是：
left == right（两个指针指向同一个位置）left > right（两个指针错开）
快慢指针：又称为龟兔赛跑算法，其基本思想就是使用两个移动速度不同的指针在数组或链表等序列结构上移动。
这种方法对于处理环形链表或数组非常有用。
其实不单单是环形链表或者是数组，如果我们要研究的问题出现循环往复的情况时，均可考虑使用快慢指针的思想。
快慢指针的实现方式有很多种，最常用的一种就是：
- 在一次循环中，每次让慢的指针向后移动一位，而快的指针往后移动两位，实现一快一慢。
283. 移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]
示例 2:
输入: nums = [0]
输出: [0]
提示:
1 <= nums.length <= 104-231 <= nums[i] <= 231 - 1
解题思路
在本题中，我们可以用一个 cur 指针来扫描整个数组，另一个 dest 指针用来记录非零数序列
的最后一个位置。根据 cur 在扫描的过程中，遇到的不同情况，分类处理，实现数组的划分。
可以理解为将数组分为三块
[0, dest] [dest+1, cur-1] [cur, n-1]
在 cur 遍历期间 , [0, dest] 这个区域的数据是 非零数据, [dest+1, cur-1] 这个区域的数据都是 0 , [cur, n-1] 则是未处理区域
算法流程:
- 初始化
cur = 0（用来遍历数组），dest = -1（dest 指向非零元素序列的最后一个位置。因为刚开始我们不知道最后一个非零元素在什么位置，因此初始化为 0 ） - cur 依次往后遍历每个元素，遍历到的元素会有下面两种情况：
- 遇到的元素是 0 ，
cur直接++。因为我们的目标是让[dest + 1, cur - 1]内的元素全都是零，因此当cur遇到0的时候，直接++，就可以让 0 在 cur - 1的位置上，从而在[dest + 1, cur - 1]内； - 遇到的元素不是 0 ，
dest++，并且交换cur位置和dest位置的元素，之后让cur++，扫描下一个元素。dest++之后，指向的元素就是 0 元素（因为非零元素区间末尾的后一个元素就是0 ），因此可以交换到cur所处的位置上，实现[0, dest]的元素全部都是非零元素，[dest + 1, cur - 1]的元素全是零。
- 遇到的元素是 0 ，
C++代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int dest = 0;
for(int cur = 0 ; cur < nums.size() ; cur++)
{
if(nums[cur] != 0) // // 处理非零元素, 与dest下标处的数据进行交换
swap(nums[dest++] , nums[cur]);
}
}
};
1089. 复写零
题目描述
给你一个长度固定的整数数组 arr ，请你将该数组中出现的每个零都复写一遍，并将其余的元素向右平移。
注意：请不要在超过该数组长度的位置写入元素。请对输入的数组 就地 进行上述修改，不要从函数返回任何东西。
示例 1：
输入： arr = [1,0,2,3,0,4,5,0]
输出：[1,0,0,2,3,0,0,4]
解释： 调用函数后，输入的数组将被修改为：[1,0,0,2,3,0,0,4]
示例 2：
输入： arr = [1,2,3]
输出：[1,2,3]
解释： 调用函数后，输入的数组将被修改为：[1,2,3]
解题思路
如果从前向后进行原地复写操作的话，由于 0 的出现会复写两次，导致没有复写的数被覆盖掉。因此我们选择从后往前的复写策略。
但是从后向前复写的时候，我们需要找到最后一个复写的数，因此我们的大体流程分两步：
- 先找到最后一个复写的数；
- 然后从后向前进行复写操作。
算法流程
- 初始化两个指针
cur = 0，dest = -1( dest 指向非零元素序列的最后一个位置。因为刚开始我们不知道最后一个非零元素在什么位置，因此初始化为 -1 ）； - 找到最后一个复写的数：
- 当
cur < n的时候，一直执行下面循环： - 判断
cur位置的元素:- 如果是 0 的话，
dest往后移动两位； - 否则，
dest往后移动一位。
- 如果是 0 的话，
- 判断
dest时候已经到结束位置，如果结束就终止循环； - 如果没有结束，
cur++，继续判断。
- 当
- 判断
dest是否越界到n的位置：- 如果越界，执行下面三步：
n - 1位置的值修改成 0 ；cur向移动一步；dest向前移动两步。
- 如果越界，执行下面三步：
- 从
cur位置开始往前遍历原数组，依次还原出复写后的结果数组：- 判断
cur位置的值：- 如果是 0 ：
dest以及dest - 1位置修改成 0 ，dest -= 2； - 如果非零：
dest位置修改成 0 ，dest -= 1；
- 如果是 0 ：
cur--，复写下一个位置。
- 判断
C++代码
class Solution {
public:
void duplicateZeros(vector<int>& arr) {
int cur = 0, dest = -1;
int n = arr.size();
// 先找到最后一个数
while (cur < n) {
if (arr[cur] != 0)
dest++ ;
else
dest += 2;
if (dest >= arr.size() - 1)
break;
cur++;
}
// 处理一下边界情况
if (dest == n) {
arr[n - 1] = 0;
dest -= 2;
cur--;
}
// 从后向前完成复写操作
while (cur >= 0) {
if (arr[cur] != 0)
arr[dest--] = arr[cur--];
else {
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
}
}
};
202. 快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
快乐数 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入： n = 19
输出： true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入： n = 2
输出： false
提示：
1 <= n <= 231 - 1
解题思路
为了方便叙述，将对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和这一个
操作记为 x 操作；
题目告诉我们，当我们不断重复 x 操作的时候，计算一定会死循环，死的方式有两种：
- 情况一：一直在 1 中死循环，即 1 -> 1 -> 1 -> 1......
- 情况二：在历史的数据中死循环，但始终变不到 1
由于上述两种情况只会出现一种，因此，只要我们能确定循环是在情况一中进行，还是在情
况二中进行，就能得到结果。
简单证明
a. 经过一次变化之后的最大值 9^2 * 10 = 810 ( 2^31-1=2147483647 。选一个更大的最
大 9999999999 )，也就是变化的区间在[1, 810] 之间；
b. 根据鸽巢原理，一个数变化 811 次之后，必然会形成一个循环；
c. 因此，变化的过程最终会走到一个圈里面，因此可以用快慢指针来解决。
算法流程
根据上述的题目分析，我们可以知道，当重复执行 x 的时候，数据会陷入到一个循环之中。而快慢指针有一个特性，就是在一个圆圈中，快指针总是会追上慢指针的，也就是说他们总会相遇在一个位置上。如果相遇位置的值是 1 ，那么这个数一定是快乐数；如果相遇位置不是 1的话，那么就不是快乐数。
- 把数
n每一位的数提取出来：
- 循环迭代下面步骤：
int t = n % 10提取个位；n /= 10干掉个位；
- 直到
n的值变为 0 ；
- 提取每一位的时候，用一个变量
tmp记录这一位的平方与之前提取位数的平方和
tmp = tmp + t * t
C++代码
class Solution {
public:
int getNextNum(int n) // 返回 n 这个数每一位上的平方和, 也就是下一个数
{
int sum = 0;
while (n)
{
int t = n % 10;
sum += t * t;
n /= 10;
}
return sum;
}
bool isHappy(int n)
{
int slow = n;
int fast = getNextNum(n);
while (slow != fast) //如果相遇位置的值是 1 ，那么这个数一定是快乐数；如果相遇位置不是 1的话，那么就不是快乐数。
{
slow = getNextNum(slow);
fast = getNextNum(getNextNum(fast));
}
return slow == 1;
}
};
11. 盛最多水的容器
题目描述
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明： 你不能倾斜容器。
示例 1：
输入：[1,8,6,2,5,4,8,3,7]
输出： 49
解释： 图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。
示例 2：
输入： height = [1,1]
输出： 1
解题思路
设两个指针 left ， right 分别指向容器的左右两个端点，此时容器的容积 :
v = (right - left) * min( height[right], height[left])
容器的左边界为 height[left] ，右边界为 height[right] 。
为了方便叙述，我们假设 左边边界小于右边边界 。
如果此时我们固定一个边界，改变另一个边界，水的容积会有如下变化形式：
- 容器的宽度一定变小。
- 由于左边界较小，决定了水的高度。如果改变左边界，新的水面高度不确定，但是一定不会超过右边的柱子高度，因此容器的容积可能会增大。
- 如果改变右边界，无论右边界移动到哪里，新的水面的高度一定不会超过左边界，也就是不会超过现在的水面高度，但是由于容器的宽度减小，因此容器的容积一定会变小的。
由此可见，左边界和其余边界的组合情况都可以舍去。所以我们可以left++跳过这个边界，继
续去判断下一个左右边界。
当我们不断重复上述过程，每次都可以舍去大量不必要的枚举过程，直到 left 与 right 相
遇。期间产生的所有的容积里面的最大值，就是最终答案。
C++代码
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0 , right = height.size() - 1;
int result = 0;
while(left < right)
{
int v = min(height[left] , height[right]) * (right - left); // 获得容积
result = v > result ? v : result; // 获得最大容积
if(height[left] < height[right])
left++;
else
right-- ;
}
return result;
}
};
611. 有效三角形的个数
题目描述
给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
示例 1:
输入: nums = [2,2,3,4]
输出: 3
解释:有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:
输入: nums = [4,2,3,4]
输出: 4
提示:
1 <= nums.length <= 10000 <= nums[i] <= 1000
解题思路
解法一: 暴力枚举
不必多说, 三层for循环走起, 枚举出所有的三元组，并且判断是否能构成三角形.
虽然说是暴力求解，但是还是想优化一下：
判断三角形的优化：
- 如果能构成三角形，需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。
- 因此我们可以先将原数组排序，然后从小到大枚举三元组，一方面省去枚举的数量，另一方面方便判断是否能构成三角形。
class Solution {
public:
int triangleNumber(vector<int>& nums) {
// 1. 排序
sort(nums.begin(), nums.end());
int n = nums.size(), ret = 0;
// 2. 从小到大枚举所有的三元组
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
// 当最小的两个边之和大于第三边的时候，统计答案
if (nums[i] + nums[j] > nums[k])
ret++;
}
}
}
return ret;
}
};
解法二: 排序+双指针
- 先将数组排序
- 根据解法一中的优化思想，我们可以固定一个最长边，然后在比这条边小的有序数组中找出一个二元组，使这个二元组之和大于这个最长边。由于数组是有序的，我们可以利用对撞指针来优化。
- 设最长边枚举到
i位置，区间[left, right]是i位置左边的区间（也就是比它小的区间）- 如果
nums[left] + nums[right] > nums[i]：- 说明
[left, right - 1]区间上的所有元素均可以与nums[right]构成比nums[i]大的二元组 - 满足条件的有
right - left种 
- 此时
right位置的元素的所有情况相当于全部考虑完毕，right--，进入下一轮判断
- 说明
- 如果
nums[left] + nums[right] <= nums[i]：
- 说明
left位置的元素是不可能与[left + 1, right]位置上的元素构成满足条件的二元组 left位置的元素可以舍去，left++进入下轮循环
- 如果
C++代码
class Solution {
public:
int triangleNumber(vector<int>& nums) {
//将数组优化为有序
sort(nums.begin() , nums.end());
int result = 0; //存放结果
int n = nums.size();
for(int i = n-1 ; i > 1; i-- )
{
int left = 0 ;
int right = i - 1;
while(left < right)
{
if(nums[left] + nums[right] > nums[i])
{
result += (right - left); //满足条件则说明[left ,right-1]区间内的所有元素都满足条件, 因为排序
right--; //此时 right 位置的元素的所有情况相当于全部考虑完毕， right-- ，进入下一轮判断
}
else //如果 nums[left] + nums[right] <= nums[i]
{
left++; //说明 left 位置的元素是不可能与 [left + 1, right] 位置上的元素构成满足条件的二元组,left++ 进入下轮循环
}
}
}
return result;
}
};
LCR 179. 查找总价格为目标值的两个商品
题目描述
购物车内的商品价格按照升序记录于数组 price。请在购物车中找到两个商品的价格总和刚好是 target。若存在多种情况，返回任一结果即可。
示例 1：
输入： price = [3, 9, 12, 15], target = 18
输出：[3,15] 或者 [15,3]
示例 2：
输入： price = [8, 21, 27, 34, 52, 66], target = 61
输出：[27,34] 或者 [34,27]
提示：
1 <= price.length <= 10^51 <= price[i] <= 10^61 <= target <= 2*10^6
解题思路
注意到本题是升序的数组，因此可以用对撞指针优化时间复杂度。
算法流程
- 初始化
left，right分别指向数组的左右两端（这里不是我们理解的指针，而是数组的下
标） - 当
left < right的时候，一直循环- 当
nums[left] + nums[right] == target时，说明找到结果，记录结果，并且返回； - 当
nums[left] + nums[right] < target时：- 对于
nums[left]而言，此时nums[right]相当于是nums[left]能碰到的最大值（别忘了，这里是升序数组哈~）。如果此时不符合要求，说明在这个数组里面，没有别的数符合nums[left]的要求了（最大的数都满足不了你，你已经没救了）。因此，我们可以大胆舍去这个数，让left++，去比较下一组数据； - 那对于
nums[right]而言，由于此时两数之和是小于目标值的，nums[right]还可以选择比nums[left]大的值继续努力达到目标值，因此 right 指针我们按兵不动；
- 对于
- 当
nums[left] + nums[right] > target时，同理我们可以舍去nums[right]（最小的数都满足不了你，你也没救了）。让right--，继续比较下一组数据，而left指针不变（因为他还是可以去匹配比nums[right]更小的数的）。
- 当
C++代码
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left = 0;
int n = price.size();
int right = n - 1;
while(left < right)
{
int sum = price[left] + price[right];
if(sum == target)
return {price[left] , price[right]};
else if (sum > target)
right--;
else
left++;
}
return {-1 , -1};
}
};
15. 三数之和
题目描述
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意： 答案中不可以包含重复的三元组。
示例 1：
输入： nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入： nums = [0,1,1]
输出：[]
解释： 唯一可能的三元组和不为 0 。
示例 3：
输入： nums = [0,0,0]
输出：[[0,0,0]]
解释： 唯一可能的三元组和为 0 。
解题思路
排序+双指针
与两数之和稍微不同的是，题目中要求找到所有不重复的三元组。那我们可以利用在两数之和
那里用的双指针思想，来对我们的暴力枚举做优化：
- 先排序, 使数组有序后方便之后操作；
- 然后固定一个数
i - 在这个数后面的区间内，使用双指针算法快速找到两个数之和等于
-a即可(也可nums[i] + nums[left] + nums[right] = 0)。
但是要注意的是，这道题里面需要有去重操作
- 找到一个结果之后，
left和right指针要跳过重复的元素； - 当使用完一次双指针算法之后，固定的
i也要跳过重复的元素。 - 注意: 去重操作需要进行边界控制
算法流程
C++代码
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin() , nums.end());
vector<vector<int>> result;
for(int i = 0 ; i < nums.size();)
{
if(nums[i] > 0) break; // 小优化: 当nums[i]大于0时,说明无符合题干的数据了
int left = i + 1;
int right = nums.size() -1;
int target = -nums[i];
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum < target)
left++;
else if (sum > target)
right--;
else{ // 符合题干的数据
result.push_back({nums[i], nums[left] , nums[right]});
left++;
right--;
while(left < right && nums[left] == nums[left-1] ) left++; // left去重并处理越界
while(left < right && nums[right] == nums[right+1]) right--; // right去重并处理越界
}
}
i++;
while( i < nums.size() && nums[i] == nums[i - 1]) i++; // i 去重并处理越界
}
return result;
}
};
18. 四数之和
题目描述
给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：
0 <= a, b, c, d < na、b、c和d互不相同nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1：
输入： nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入： nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]
解题思路
- 先排序
- 依次固定一个数
i； - 在这个数
i的后面区间上，利用三数之和找到三个数，使这三个数的和等于target
算法流程
C++代码
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
int n = nums.size();
for(int i = 0 ; i < n ;)
{
// 利用 三数之和
for( int j = i + 1 ; j < n ; )
{
//if(nums[j] > 0) break;
int left = j + 1;
int right = n - 1;
while(left < right)
{
long long sum = (long long)nums[i] + nums[j] +nums[left] + nums[right];
if(sum < target)
left++;
else if (sum > target)
right--;
else
{
result.push_back({nums[i] , nums[j] , nums[left] , nums[right]});
left++;
right--;
while(left < right && nums[left] == nums[left-1] ) left++; //left 去重
while(left < right && nums[right] == nums[right+1]) right--; // right 去重
}
}
j++;
while(j < n && nums[j] == nums[j-1] )j++; // j 去重
}
i++;
while(i < n && nums[i] == nums[i-1]) i++; // i 去重
}
return result;
}
};