283. 移动零 - 力扣LeetCode数组分块问题用双指针。[0, dst] [dst 1, i - 1] [i, n - 1]分别是!00待扫描。class Solution { public: void moveZeroes(vectorint nums) { int src -1, i 0; int n nums.size() - 1; while(i n) { if(nums[i]) swap(nums[src], nums[i]); i; } } };1089. 复写零 - 力扣LeetCode原地修改数组数据用双指针。一开始上来无法直接找到如何使用双指针的方法就可以先异地操作模拟一下过程之后再优化成原地操作。从前往后复写会产生数据的覆盖因此选择从后往前复写。问题遇到边界情况时为什么要将arr[n - 1]的位置设置成0因为遇到边界情况无非就是arr[cur]为0了之后导致dst往后走了两步从而越界了那我们就需要回退到相当于是上一个边界情况那里但是回退前得需要将这次越界的情况也要复写一下呀分别是n-1和n位置要复写为0但是n位置已经越界了因此只需要将n-1位置复写成0即可。具体还可以结合下文图片以及力扣上的样例去画画图。class Solution { public: void duplicateZeros(vectorint arr) { //1.找最后一个复写的数 int dst -1, cur 0; int n arr.size(); while(cur n) { if(arr[cur]) dst; else dst 2; if(dst n - 1) break; cur; } //处理边界情况---回退到上一步 if(dst n) { arr[n - 1] 0; dst - 2; --cur; } //2.从后往前开始复写 while(cur 0 dst 0) { if(arr[cur]) { arr[dst--] arr[cur]; } else { arr[dst--] 0; arr[dst--] 0; } --cur; } } };202. 快乐数 - 力扣LeetCode这种题得找规律因为你不可能学过如何判断一个数字是否能在经过题目说的那种操作之后变成1。如下所示是题目给出的两个示例我将它一直按照题给操作一直循环之后得到的结果会发现能变成1的最后会出现1相当于就是进入一个值全为1的环。不能变成1的到最后也会产生一个环(因为题目说了如果变不到1就会无限循环如果题目不说会无限循环就会产生第三种情况就是一直变化下去永不成环)。归根到底这两种情况到最后都会产生一个环因此这个问题就变成了判断链表是否带环那题几乎一样了用快慢双指针的方式去做只要两个指针相遇就说明链表一定带环但是本题我们已经敢保证一定是带环的所以只要判断双指针的相遇点(一定在环里)是否是1或者不是1就行是1就是快乐数不是1就不是快乐数。但是现在有一个问题思路已经有了我们这个所谓的链表如何来呢链表那道题的指针是定义成Node*的我们这里不用真的去定义指针就拿19为头的那个链表举例子初始化时定义slow为19fast为19接下去往后走就是slow更新成82fast更新成68......就是直接将slow和fast更新成下一个结果不就相当于往后走了一步嘛。class Solution { public: int bitSum(int n) { int t 0; while(n) { t pow(n % 10, 2); n / 10; } return t; } bool isHappy(int n) { //如果这样定义的话循环压根不成立 //int slow n, fast n; //slow和fast从哪里开始不要紧但是必须得给我一个走一步一个走两步 int slow n, fast bitSum(n); while(slow ! fast) { slow bitSum(slow); fast bitSum(bitSum(fast)); } if(fast 1) return true; return false; } };11. 盛最多水的容器 - 力扣LeetCode看到这道题首先想到的一定是一种暴力解法就是将枚举出所有的面积然后比比谁最大但这样做是一定会超时的。一般来说做题一上来没思路可以去尝试找找规律就像上边那题一样顺着题给的数据发现了在数据枚举的过程中一定会带环并且环里要么1要么!1。找到了规律之后其实就可以省掉好多暴力解法里枚举的情况因此可以用双指针一个指向区间最开头一个指向区间结尾算出当前这个面积然后指向区间高度那一侧的指针--或者计算下一段区间每次算出来比较大小直至指针相遇。总结一下本题用到的是利用单调性双指针。class Solution { public: int maxArea(vectorint height) { int n height.size(); int l 0, r n - 1; int ret 0; while(l r) { int s (r - l) * min(height[l], height[r]); ret max(ret, s); if(height[l] height[r]) l; else --r; } return ret; } };611. 有效三角形的个数 - 力扣LeetCode题目意思就是在数组里找到所有能构成三角形的组合。首先得知道怎么判断三个数是否能构成三角形三个数里任意两个数相加都得大于第三边也就是要比较三次才行这样一来时间复杂度肯定是很高的又要枚举所有的情况并且每枚举出一种情况都要比较三次(如下)。有了上边的暴力解法我们就可以尝试优化一下它无非就是优化比较三次和枚举的数量如果我们将数据排成升序那么其实两个较小的相加大于第三个就说明这三个数构成三角形了这样一来就只要比较一次了。另外此时数据已经有序了就可以利用单调性双指针去解决问题。优化之后时间复杂度为O(N^2)。class Solution { public: int triangleNumber(vectorint nums) { int n nums.size(); sort(nums.begin(), nums.end()); int maxi n - 1; int ret 0; //如果取maxi小于下标2的话都没有三条边了 while(maxi 2) { int left 0, right maxi - 1; while(left right) { if(nums[left] nums[right] nums[maxi]) { ret right - left; --right; } else { left; } } --maxi; } return ret; } };LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode本题的数组已经有序直接利用单调性初始化时l指向0位置r指向n-1位置计算lr的值总共有三种情况。其中的情况是我们想要的直接返回。如果是就r--因为根据单调性目前情况已经是了只有r--去指向较小的数字的时候再跟l相加才有可能是的。如果是就l同理。class Solution { public: vectorint twoSum(vectorint price, int target) { int n price.size(); int l 0, r n - 1; while(l r) { if(price[l] price[r] target) { --r; } else if(price[l] price[r] target) { l; } else { //initializer_list构造加拷贝构造 return {price[l], price[r]}; } } //没有合适的就返回匿名空vector即可 return vectorint(); } };15. 三数之和 - 力扣LeetCode先搞清楚题目意思题目总共给了三个条件i ! ji ! kj ! k的意思就是不能选两个相同下标位置的元素题目还要求选出来的三数之和为0最后一个要求就是选出来的三元组不能重复。拿示例一说明[-1, 0, 1]和[0, 1, -1]是重复的三元组得去掉一种。解法一就是暴力解法三层循环枚举出全部的三元组满足和为0且不是同一个下标位置的条件但是得去掉重复的三元组如何去重呢可以借助unordered_set我们可以先将选出来的三元组排序如果是两个相同的三元组那么排完序后就是相同的存入容器容器就自动帮我们去重了。但由于有三层循环的存在时间复杂度是非常高的我们就可以借助排完序后的有序数组来优化时间复杂度一旦是有序的数组我们就可以用双指针来优化思路跟上文的那道有效的三角形个数很像先固定一个数然后定义双指针根据数组单调性去筛选出一些三元组。扩展一下如果不用容器去去重我们可以怎么办呢其实无非就是利用指针与数组有序的特性假设固定k之后我们找到了一组再lr--之后再次去找此时如果l/r位置的元素就是上一次的元素就可以直接跳过了举个例子。优化之后不管是用容器去重还是用指针去重时间复杂度都是O(N^2)。// class Solution { // public: // vectorvectorint threeSum(vectorint nums) { // //unordered_set不支持vector作为key没有哈希函数支持 // //unordered_setvectorint s; // //具体容器内怎么排序其实并不关心重点是要去重 // setvectorint s; // sort(nums.begin(), nums.end()); // int n nums.size(); // int k 0; // while(k n - 2) // { // int l k 1, r n - 1; // //必须要是不同的下标l不能等于r // while(l r) // { // if(nums[l] nums[r] -nums[k]) // { // --r; // } // else if(nums[l] nums[r] -nums[k]) // { // l; // } // else // { // //排完序后的数组klr的下标顺序就是有序的了 // //找到解之后要移动指针l和r // //因为这次找到仅仅只是找到[l, r]中的一组而已 // s.insert({nums[k], nums[l], nums[r]}); // l; // --r; // } // } // k; // } // //返回匿名对象 // return vectorvectorint(s.begin(), s.end()); // } // }; //不借助容器去重 class Solution { public: vectorvectorint threeSum(vectorint nums) { sort(nums.begin(), nums.end()); vectorvectorint ret; int n nums.size(); int k 0; while(k n - 2) { int l k 1, r n - 1; //必须要是不同的下标l不能等于r while(l r) { if(nums[l] nums[r] -nums[k]) { --r; } else if(nums[l] nums[r] -nums[k]) { l; } else { //排完序后的数组klr的下标顺序就是有序的了 //找到解之后要移动指针l和r //因为这次找到仅仅只是找到[l, r]中的一组而已 ret.push_back({nums[k], nums[l], nums[r]}); //去重别忘了防越界 while(l r nums[l] nums[l 1]) l; while(l r nums[r] nums[r - 1]) --r; l; --r; } } k; //进入下一次循环前先去重 while(k 0 k n - 2 nums[k] nums[k - 1]) k; } return ret; } };18. 四数之和 - 力扣LeetCode本题和上一题差不多无非就是排序双指针去重只不过要多加一层循环多固定一个数因为现在是四数之和。其他都一样。class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint ret; sort(nums.begin(), nums.end()); int n nums.size(); //注意i要n-4因为总共要找4个数 for(int i 0;i n - 4;) { for(int j i 1;j n - 3;) { int l j 1, r n - 1; while(l r) { //四个int相加会溢出所以强转 //不要这样写(long long)(nums[i] nums[j] nums[l] nums[r]) //因为这样就是对整体结果强转已经溢出了你再强转也没用啊 //强转一个后边的运算全部会整型提升的 long long sum (long long)nums[i] nums[j] nums[l] nums[r]; if(sum target) { --r; } else if(sum target) { l; } else { //加入结果去重 ret.push_back({nums[i], nums[j], nums[l], nums[r]}); while(l r nums[l] nums[l 1]) l; while(l r nums[r] nums[r - 1]) --r; l; --r; } } //为了避免下边的去重操作跟for循环里的j冲突因此把j移动到这里 j; while(j i 1 j n - 3 nums[j] nums[j - 1]) j; } i; while(i 0 i n - 4 nums[i] nums[i - 1]) i; } return ret; } };