目录
题目一：移动零
题目二：复写零
题目三：快乐数
题目四：盛最多水的容器
题目五：有效三角形的个数
题目六：和为s的两个数字(剑指offer)
题目七：三数之和
题目八：四数之和
常见的双指针有两种形式，一种是对撞指针，一种是快慢指针
这里的指针并不是int*这种指针，而是利用数组下标来充当指针
对撞指针：一般用于顺序结构中，也称左右指针
对撞指针从两端向中间移动。⼀个指针从最左端开始，另⼀个从最右端开始，然后逐渐往中间逼 近
快慢指针：其基本思想就是使用两个移动速度不同的指针在数组或链表等序列 结构上移动
最常用的⼀种快慢指针就是：在⼀次循环中，每次让慢的指针向后移动⼀位，而
快的指针往后移动两位，实现⼀快⼀慢
下面看具体例子：
题目一：移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums =[0,1,0,3,12]输出:[1,3,12,0,0]
示例 2:
输入: nums =[0]输出:[0]
设置两个指针，分别是cur和dest
两个指针的作用:
cur：从左往右扫描数组，遍历数组
dest：已处理的区间内，非零元素的最后一个位置
cur从前往后遍历的过程中:
遇到0元素:
cur++；
遇到非零元素:
swap(dest + 1, cur)；dest+ +, cur+ +;
代码为：
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int cur = 0,dest = -1;
while(cur < nums.size())
{
if(nums[cur] != 0)
{
dest++;
swap(nums[dest],nums[cur]);
}
cur++;
}
}
};题目二：复写零
给你一个长度固定的整数数组 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]
这道题最简单的就是创建一个新数组，然后随着原数组的cur指针遍历，在新数组中插入，但是条件是就地修改，所以放弃该方法
这道题不能再跟着cur指针从前向后遍历，因为在当前数组中，如果是从前向后遍历，当出现0时，连续复写0，会将下一个非0元素覆盖，导致结果出错
所以方法是：
①先找到最后一个"复写"的数
②从后向前"完成复写操作
从后向前复写时不会覆盖非0元素，因为从后向前遍历时，我们是经过计算，知道最后一个"复写"的数的位置，所以不会出现上述情况
找到最后一个复写的数的位置：
①先判断cur位置的值
②决定dest向后移动一步或者两步(cur是0移动2步，非0移动1步)
③判断一下dest是否已经到结束为止
④cur++
这里会有一个特殊情况，需要处理边界情况，如下这种情况：
dest会指向最后一个位置的下一个位置，此时只需要改变下标为n-1位置的元素，cur--后，dest-=2即可
此时cur指向的就是最后一个复写的数
代码如下：
class Solution {
public:
void duplicateZeros(vector<int>& arr)
{
int cur = 0, dest = -1, n = arr.size();
// 找到最后一个复写的数位置
for (int i = 0; i < n; ++i)
{
if (arr[cur])
dest++;
else
dest += 2;
if (dest >= n - 1)
break;
cur++;
}
// 特殊情况判断dest是否指向数组最后一个元素的下一个位置
if(dest == n)
{
arr[n-1]=0;
cur--;
dest-=2;
}
// 从后向前完成复写操作
while (cur >= 0)
{
if (arr[cur] == 0)
{
arr[dest--] = 0;
arr[dest--] = 0;
cur--;
}
else
arr[dest--] = arr[cur--];
}
}
};需要注意一点，arr.size()是unsigned int类型的，我在第一次编写代码时直接用dest与arr.size()作比较，这里就会出现不同类型在混合运算中相互转换，有符号会转为无符号数
dest初始值为-1，如果将dest转换为无符号数，那就变为了整型的最大值，所以就与我想要的结果截然不同了，所以提前使用int n = arr.size()，避免出现类型转换
题目三：快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19 输出：true 解释： 1^2 + 9^2 = 82 8^2 + 2^2 = 68 6^2 + 8^2 = 100 1^2 + 0^2 + 0^2 = 1
示例 2：
输入：n = 2 输出：false
初步一看，这种题和双指针有什么关系呢，其实则不然，可以抽象为链表中判断链表是否有环的情况，下面具体解释：
例如上面例子的19，可以抽象为下面这种环的问题，环中都是1，所以符合条件
而n如果是2，就变为了：
所以解法还是快慢双指针的方法：
①定义快慢指针
②慢指针每次向后移动一步，快指针每次向后移动两步
③判断相遇时候的值即可(为1则满足条件，否则不满足)
代码如下：
class Solution {
public:
//计算n的每一位平方和的结果
int calculate(int n)
{
int res = 0;
while(n)
{
int tmp = n%10;
res += tmp*tmp;
n/=10;
}
return res;
}
bool isHappy(int n)
{
//初始slow指向第一个数，fast指向第二个数
int slow = n;
int fast = calculate(n);
while(slow != fast)
{
//slow走1步，fast走2步
slow = calculate(slow);
fast = calculate(calculate(fast));
}
return slow == 1;
}
};题目四：盛最多水的容器
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明：你不能倾斜容器。
首先，再看到这个题的时候，最容易想到的就是暴力枚举，两层for循环，将每一种情况都列出来，然后选出最大的情况即可，但是这种情况就没必要实践了，因为一定会超时的，O(N^2)的时间复杂度，这道题当然不是考你一个暴力方法结题了，所以方法如下
利用单调性，使用双指针思想解决：
先举个例子，比如说数组是[8, 6, 2, 5]，我们取两端的数据组成水的体积，此时8和5组合的水的体积是：高 * 宽 = 5 * 3 = 15
此时我们取两端的数据较小的那一个，即为5，此时5可以和2、6、8组合，这里可以思考一下：
如果5和2组合会导致：高度下降，宽度下降，那么结果水的体积肯定也下降
如果5和6组合会导致：高度不变，宽度下降，那么结果水的体积肯定也下降
所以我们可以很轻松推出一个结论：两端较小的那一个数，在和其他数进行组合时，无论是和大于它的还是小于它的数组合，都会导致水的体积下降
所以我们比较两端的数组合时，只考虑大的那一个数即可，将较小数排除，记录此时的水体积，最后两端的指针相遇时，比较每次记录的结果，取最大的那一个就是题目的要求
上述的方法时间复杂度为O(N)，效率远远高于暴力枚举
代码如下：
class Solution {
public:
int maxArea(vector<int>& height) {
int left = 0,right = height.size()-1;
int ret = 0;//ret是当前的最大体积
while(left != right)
{
int h = min(height[left],height[right]);//高度
int w = right - left;//宽度
int v = h * w;//体积
ret = max(ret,v);//取当前的体积和ret中记录的最大的那一个
if(height[left] < height[right]) left++;
else right--;
}
return ret;
}
};题目五：有效三角形的个数
给定一个包含非负整数的数组 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
给我们三个数，判断是否能够构成三角形
这个大家都知道，即任意两边之和大于第三边，但是如果知道三条边的大小关系，即三条边从小到大分别是abc，此时只需判断a+b>c这个关系即可判断是否能构成三角形
因为c是最大的，c本身就大于其他两条边，那么c加其中一个边也一定大于另一个边，这是恒成立的
解法一：最容易想到的就是暴力枚举，直接写三层for循环，把每一个三元组都枚举出来，判断能否构成三角形，这里的时间复杂度是O(N^3)，
解法二：利用单调性，使用双指针算法来解决问题
1.先固定最大的数n
2.在最大的数的左区间内，使用双指针算法，快速统计出符合要求的三元组的个数
下面举例子说明这个方法：
有一个有序数组，假设是[2, 3, 4, 5, 6]，先固定最大的数6，此时取6左边区间内的最大数和最小数，即2和5，分别指定left指向2，right指向5
计算2+5>6是否成立，如果2+5都成立了，那么就不需要向右取3,4和5组合了，因为3,4是大于2的，所以3+5/4+5也一定大于6，所以这一种情况就有了right-left=3-0=3种解，即2+5/3+5/4+5，下一步就是right--，继续上述步骤
反之，如果left和right所指向的值不大于最大数n，此时left++，判断是否大于，如果大于就重复上述步骤，如果小于继续left++，直到left与right相遇
当left和right相遇，这一次固定最大数n的情况就处理完毕，n变为它左边倒数第二大的数，继续重复上述步骤
所以[2, 3, 4, 5, 6]中，先指定n为6，left指向2，right指向5，发现2+5>6，即有right-left = 3-0 = 3种解，分别是{2,5,6}、{3,5,6}、{4,5,6}
接着right--，指向4，left指向2，2+4=6不大于6，所以left++，left指向3，此时3+4大于6，满足要求，此时有right-left = 2-1 = 1种解，即{3,4,6}
接着right--，指向3，left指向2，2+3 = 5不大于6，所以left++，也指向3，left和right相遇，此次n的情况结束
接下来n变为5，left指向2，right指向4，2+4 = 6 > 5，满足要求，此时有right-left = 2-0 = 2种解，分别是{2,4,5}、{3,4,5}
接着right--，指向3，left指向2，2+3=5不大于5，所以left++，left也指向3，eft和right相遇，此次n的情况结束
接下来n变为4，left指向2，right指向3，2+3 = 5 > 4，满足要求，此时有right-left = 1-0 = 1种解，分别是{2,3,4}
接着right--，指向2，left和right相遇，此次n的情况结束
接下来n变为3,2都不满足要求，所以解题结束，共有7种组合，分别是：
{2,5,6}、{3,5,6}、{4,5,6}、{3,4,6}、{2,4,5}、{3,4,5}、{2,3,4}
该方法的时间复杂度为O(N^2)，即两层循环，最大值n一层，里面left和right一层，相比于暴力枚举的O(N^3)，效率大大提升
代码如下：
class Solution {
public:
int triangleNumber(vector<int>& nums) {
sort(nums.begin(),nums.end());//数组排序
int ret = 0;//ret返回最终结果
//外层循环表示n的取值，从最大的往左取
for(int i = nums.size()-1; i >= 2; --i)
{
int left = 0, right = i-1;
//里层循环left和right相遇时就停止
while(left != right)
{
if(nums[left]+nums[right] > nums[i])
{
ret += right-left;
right--;
}
else
left++;
}
}
return ret;
}
};题目六：和为s的两个数字(剑指offer)
该题目是剑指offer的一道题
购物车内的商品价格按照升序记录于数组 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]
同样第一种是暴力解法， 也就是两层for循环，全部情况都枚举一遍，来判断是否符合题意，效率比较低，就不详细说了
这道题比较简单，既然数组是有序的了，那就很容易能想到，定义left和right指针，分别指向两边的值，如果两边的值相加小于target，那就left++，如果大于target，那就right--，如果等于，就得到结果
代码如下：
class Solution {
public:
vector<int> twoSum(vector<int>& price, int target) {
int left = 0, right = price.size()-1;
vector<int> v;
while(left != right)
{
int sum = price[left] + price[right];
if(sum > target)
right--;
else if(sum < target)
left++;
else
{
v.push_back(price[left]);
v.push_back(price[right]);
break;
}
}
return v;
}
};题目七：三数之和
给你一个整数数组 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
此题的要求也就是选出的三个数不能重复，且观察示例一，[-1,0,1]和[0,1,-1]虽然都是0，且三个数的下标并不完全重复，但是这三个数都包含了0,-1,1，所以只取其中一个即可
还有一个说明，返回的顺序并不重要，也就是你返回[-1,0,1]、[0,-1,1]、[1,-1,0]都是对的，不追究顺序问题
第一种方法同样是暴力枚举，将所有清理都枚举出来，然后去重，最后找到有效的三元组
也就是排序整个数组 + 暴力枚举 + 利用set去重，整个暴力枚举的算法时间复杂度是O(N^3)，因为暴力枚举需要三层for循环，依次取一个数
第二种方法是排序 + 双指针+ set自动去重，相比于第三种方法不需要考虑去重的操作：但是还是推荐第三种方法，因为直接用set体现不出自己去重时候的思考，面试可能会让优化
第三种方法是排序 + 双指针
首先将数组排序，固定一个a，在a右边的区间利用双指针算法找到两数之和为-a的两个数
这里可以优化的点是只需要选择a是负数的情况，因为a如果都是正数了，后面的数都比a大，肯定加起来不可能为0了
此时就找到了所有符合的三元组，还有两个细节需要注意
一是去重，二是不漏，不漏是指在a右边区间找到一个解后，不要停继续找，直到left和right相遇为止
下面说说去重怎么操作：找到一种结果之后, left 和right指针要跳过重复元素，因为如果遇到相同的数，往后找依旧会找到同样的结果
当使用完一次双指针算法之后， a也需要跳过重复元素
需要注意：在上述的指针移动操作时，可能会有极端场景，全是重复元素，可以会出现越界的情况
第二种使用set的方法如下(，不推荐，推荐第三种方法)：
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
// 排序
sort(nums.begin(), nums.end());
set<vector<int>> sv;
int n = nums.size();
// 第一层循环用于循环a
for (int i = 0; i < n; i++) {
int a = nums[i];
if (a > 0)
break;
int left = i + 1, right = n - 1;
int target = -1 * a;
// 第二层循环用于双指针算法找到另外两个数
while (left < right) {
int sum = nums[left] + nums[right];
if (sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
sv.insert({a, nums[left], nums[right]});
left++;
right--;
}
}
}
vector<vector<int>> vv(sv.begin(), sv.end());
return vv;
}
};第三种方法的代码如下：
vector<vector<int>> threeSum(vector<int>& nums)
{
//排序
sort(nums.begin(), nums.end());
vector<vector<int>> vv;
int n = nums.size();
//第一层循环用于循环a
for (int i = 0; i < n; )
{
int a = nums[i];
if (a > 0)
break;
int left = i + 1, right = n - 1;
int target = -1 * a;
//第二层循环用于双指针算法找到另外两个数
while (left < right)
{
int sum = nums[left] + nums[right];
if (sum < target)
{
left++;
}
else if (sum > target)
{
right--;
}
else
{
vv.push_back({ a,nums[left],nums[right] });
left++;
right--;
//去重left和right
while (left < right && nums[left] == nums[left - 1])
{
left++;
}
while (left < right && nums[right] == nums[right + 1])
{
right--;
}
}
}
//去重a
i++;
while (i < n && nums[i] == a)
{
i++;
}
}
return vv;
}题目八：四数之和
给你一个由 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]]
通过观察四数之和的题目，它的解法和三数之和几乎就是一样的，所以解法也是一样的：
第一种暴力解法，排序 + 暴力枚举 + 利用set去重
第二种方法：
1.依次固定一个数a
2.在a后面的区间内，利用“三数之和”找到三个数
使这三个数的和等于target - a即可
在a后面的区间内：
1.依次固定一个数b
2.在b后面的区间内，利用“双指针"找到两个数
使这两个数的和等于target- a- b即可
所以时间复杂度就是O(N^3)，因为两层for循环，中间套了一个while循环
代码如下：
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> vv;
sort(nums.begin(),nums.end());//排序
int n = nums.size();
//第一层循环用于循环a
for(int i = 0; i < n;)
{
int a = nums[i];
//第二层循环用于循环b
for(int j = i+1; j < n;)
{
int b = nums[j];
int left = j + 1, right = n - 1;
//需要注意溢出的风险
long long aim = (long long)target - a - b;
while(left < right)
{
int sum = nums[left] + nums[right];
if(sum < aim)
left++;
else if(sum > aim)
right--;
else
{
vv.push_back({a,b,nums[left],nums[right]});
left++;
right--;
//去重一
while(left < right && nums[left] == nums[left-1])
left++;
while(left < right && nums[right] == nums[right+1])
right--;
}
}
//去重二
j++;
while(j < n && nums[j] == b)
j++;
}
//去重三
i++;
while(i < n && nums[i] == a)
i++;
}
return vv;
}
};以上就是双指针相关的算法题练习了
