双指针1、移动零1.1、题目理解1.2、原理分析1.3、代码演示2、复写零2.1、题目理解2.2、原理分析2.3、代码演示3、快乐数3.1、题目理解3.2、原理分析3.3、代码演示4、盛最多水的容器4.1、题目理解4.2、原理分析4.3、代码演示5、有效三角形的个数5.1、题目理解5.2、原理分析5.3、代码演示6、两数之和7、三数之和7.1、题目理解7.2、原理分析7.3、代码演示8、四数之和8.1、题目理解8.2、原理分析8.3、代码演示1、移动零移动零示例如下1.1、题目理解很明显题目要求我们将数组分成两部分前面一部分为非0数并且顺序不可改变后面一部分全为01.2、原理分析像这样类似数组分块的问题我们可以采用双指针的方法。我们定义int dest -1int cur 0dest全称destination有目的地、终点的意思。我们这里让dest指向下标-1意在使dest一直指向已排好的非0数序列的末端。cur全称current意为当前的、现在的。cur的作用是遍历数组。cur遍历过程中遇到下标对应值为0什么也不做遇到下标对应值非0destdest与cur对应值交换由于我们用的是for循环cur的前进就不需要另外写。我们以数组[0, 1, 0, 3, 12]为例演示一遍移动的过程1.3、代码演示classSolution{public:voidmoveZeroes(vectorintnums){for(intdest-1,cur0;curnums.size();cur)if(nums[cur]!0)swap(nums[cur],nums[dest]);}};2、复写零复写零示例如下2.1、题目理解遇到0就添加一个0所以数组[1, 0, 2, 3, 0, 4, 5, 0]应该变成[1, 0, 0, 2, 3, 0, 0, 4, 5, 0, 0]去除越界的部分就得到了[1, 0, 0, 2, 3, 0, 0, 4]2.2、原理分析我们依旧使用双指针。以数组[1, 0, 2, 3, 0, 4, 5, 0]为例。从前往后行不行呢图示过程中我们使dest 0cur 0然后cur遍历整个数组遇到非0数dest遇到0dest位置置0dest–dest位置再置0dest–。接着我们就会发现cur指向第二个“0”对dest操作完后元素“2”被覆盖掉了。所以从前往后不可行。那从后往前呢我们使dest指向数组末尾cur指向复写后数组的最后一个元素。cur开始向前遍历遇到非0cur指向数赋值给dest指向位置遇到0destdest位置置0dest–dest位置再置0dest–。就可以了。现在的问题是我们如何找到正确的cur也就是复写0后数组的最后一个元素在原来元素的位置我们还是可以使用双指针。我们定义dest -1cur 0此时cur遍历数组dest指向的是复写操作调整完之后的部分数组的末位。当cur指向非0dest前进一位当cur指向0dest前进两位。当dest指向原数组末位结束。但是还有一种情况dest会越界。比如数组[1, 0, 2, 3, 0, 4]越界时dest一定等于arr.size()此时cur一定指向了0。这时我们就要特殊处理当dest arr.size()时数组末位置0cur–dest - 2。2.3、代码演示classSolution{public:voidduplicateZeros(vectorintarr){intdest-1,cur0,narr.size();// 1.找复写后数组的最后一个数while(curn){if(arr[cur]!0)dest;elsedest2;if(destn-1)break;cur;}// 2.特殊处理if(destn){arr[n-1]0;--cur;dest-2;}// 3.复写数组while(cur0){if(arr[cur]!0)arr[dest--]arr[cur];else{arr[dest--]0;arr[dest--]0;}--cur;}}};3、快乐数快乐数3.1、题目理解以19为例画出19是快乐数的推导过程以2为例画出2不是快乐数的推导过程3.2、原理分析假设对的数的操作每一次将该数替换为它每个位置上的数字的平方和记为 f 操作。乍一看快乐数与非快乐数之间没有任何联系。但是我们从循环的角度看就可以把快乐数的推导过程与非快乐数的推导过程统一起来了对于数a当进行次若干f操作后数a最终变为1此时a无论经过多少次f操作结果都是1。此时a为快乐数。对于数b当进行次若干f操作后数a最终变为非1的数c此时b无论经过多少次f操作结果都是c。此时b不是快乐数。这时我们就可以借鉴快慢指针的做法。3.3、代码演示classSolution{public://平方和操作另外封装intFunc(intn){inthappy0;while(n){happy(n%10)*(n%10);n/10;}returnhappy;}boolisHappy(intn){//如果slow和fast都为n那么循环就进不去intslown,fastFunc(Func(n));while(slow!fast){slowFunc(slow);fastFunc(Func(fast));}returnfast1;}};4、盛最多水的容器盛最多水的容器4.1、题目理解我们以例一为例。柱状图是以数组每一位数字的下标为横坐标每一位上的数字值为纵坐标每两根柱子构成一个容器。由木桶效应得较短的柱子决定了盛水的多少而柱子的高度就是数组对应位置上的值。设数组名为height选取的数组两个位置上的值左边的值下标为left右边的下标为right。那么底L为(right - left)高h就是较小数。则最多盛水的计算公式最多盛水 ( r i g h t − l e f t ) ∗ m i n ( h e i g h t [ l e f t ] , h e i g h t [ r i g h t ] ) 最多盛水(right - left)*min(height[left], height[right])最多盛水(right−left)∗min(height[left],height[right])如上图选取数组1位置下的值8和8位置下的值7则最多盛水(8 - 1)*7 49。4.2、原理分析我们可以直接采取暴力解法将数组能生成的所有容器都列举一遍然后算出所有的容量再选出最大的一个。但是此时的时间复杂度为O(N^2)提交时可能会超时。我们可以这样思考我们取出部分数组[6, 2, 5, 4]令left指向最左边的6right指向最右边的4。此时底L为3高h为4。假设我们令left向前也就是抛弃6同时right不动。此时left指向2。那么这时left的移动过程中L和H的变化情况为底L一直减小高h在left的移动过程中可能遇到大于4的值此时h不变也可能遇到小于4的值此时h减小由公式容量V L * hleft舍弃了较大值6接下来的left无论怎么与right组合结果都减小。4.3、代码演示由此我们就可以设计代码定义双指针left指向数组首位、right指向数组末位。计算出当前容量。然后选出较小数对应指针往里靠近再计算容量。重复操作。classSolution{public:intmaxArea(vectorintheight){intleft0,rightheight.size()-1,V0;while(leftright){Vmax(V,(right-left)*min(height[left],height[right]));if(height[left]height[right])left;else--right;}returnV;}};5、有效三角形的个数有效三角形的个数5.1、题目理解比如数组[2①, 2②, 3, 4]有以下组合其中不满足的只有2, 2, 4所以有效的三元组是3个。比如数组[4, 2, 3, 4]有以下组合其中所有组合都是有效的所以有效的三元组是4个。5.2、原理分析首先我们对判断三个数是否构成三角形三条边的依据作一个优化我们之前判断三个数a, b, c是否构成三角形三条边依据是a b c abcabca c b acbacbb c a bcabca三个条件同时满足。但其实我们对a, b, c三个数进行排升序得到新序列x, y, z(x y z)。只要满足两个较小数xy z那么a, b, c(x, y, z)三个数一定能构成三角形。所以我们先对给出序列排成升序。接着使用双指针法。我们以序列[2, 2, 3, 4, 5, 9, 10]为例演示过程定义三个下标i从数组末位开始直到下标2位置结束因为是三元数遍历数组left起始指向0位置right指向i的前一个位置此时2 9 11 10。由于数组是递增的此时left从0位置开始一直到right的前一位数中每一个数与right指向数相加结果都大于10都满足构成三角形的条件。那么这时我们统计到有效三角形个数为right - left 5 - 0 5。然后–right。此时2 5 7 10不构成有效三角形。我们就让leftleft不能与right相遇。此此时有两种情况如果arr[left] arr[right]还是小于arr[i]只能再left看看有没有加和大于arr[i]的情况如果arr[left] arr[right]大于arr[i]就先统计有效三角形个数再–right此时我们可以总结方案外层循环中i遍历数组内层循环中left起始位置0right起始位置i - 1left不能与right相遇如果arr[left] arr[right] arr[i] 统计个数right - left然后–right如果arr[left] arr[right] arr[i] left5.3、代码演示classSolution{public:inttriangleNumber(vectorintnums){// 1.排序sort(nums.begin(),nums.end());// 2.统计intret0,nnums.size();for(intin-1;i2;--i){intleft0,righti-1;while(leftright){if(nums[left]nums[right]nums[i])left;elseretright-left,--right;//left后逗号不可改为分号否则分支终止}}returnret;}};6、两数之和两数之和classSolution{public:vectorinttwoSum(vectorintprice,inttarget){intnprice.size(),left0,rightn-1;while(leftright){intsumprice[left]price[right];if(sumtarget)left;elseif(sumtarget)--right;else{return{price[left],price[right]};}}return{-1,-1};}};7、三数之和三数之和7.1、题目理解怎么理解不重复以数组[-1, 0, 1, 2, -1, -4]为例。前一个-1组成的序列[-1, 0, 1]符合三数和为零后一个-1组成的序列[-1, 0, 1]也符合三数和为零。所以我们有一个去重的需求。7.2、原理分析我们可以先排序。那么这时我们可以直接枚举出所有的三元组然后使用库函数set去重。但是我们可以做更进一步的优化排完序之后我们用下标i固定一个数a。然后在剩下的序列[i1, size-1]中定义下标left, right。然后寻找left与right指向数的和是否等于a的相反数。此时问题就变为了两数之和的问题。但是有一些细节需要处理当i移动到a大于0之后由于此时数组升序之后就找不到两个数和为a的相反数。此时的i就无需讨论。不漏之前两数之和只需要我们返回一种情况即可。而本题需要我们找到所有情况所以找到一种情况后left, right应继续向里靠近继续寻找。去重找到一种情况后我们假设此时 left 指向 x, right 指向 y 。当left, right向里靠近时由于此时数组升序可能指向相同的 x, y 。这时我们应该再让left, right向里靠近。当前指向a的i如果找到了符合的情况向前遍历时可能也会找到相同的 a 这时i也要跳过。防止越界如果序列为[0, 0, 0]去重过程中left可能越界应注意控制去重处理的辅助思考7.3、代码演示参考代码classSolution{public:vectorvectorintthreeSum(vectorintnums){vectorvectorintret;//排序sort(nums.begin(),nums.end());intnnums.size();for(inti0;in;)//固定a{//升序a0a之后就肯定没有两数之和为-aif(nums[i]0)break;intlefti1,rightn-1,target-nums[i];while(leftright){intsumnums[left]nums[right];//两数之和的思路if(sumtarget)--right;elseif(sumtarget)left;else{ret.push_back({nums[left],nums[right],nums[i]});left,--right;//去重while(leftrightnums[left]nums[left-1])left;// 防止越界while(leftrightnums[right]nums[right1])--right;}}//另外对i操作i;// 防止越界while(innums[i]nums[i-1])i;}returnret;}};//我自己思路的小问题找到情况后left, right是同时向内一步的我想出的代码classSolution{public:vectorvectorintthreeSum(vectorintnums){// 1.排序// 2.固定一个数a// 3.在该数后面的区间内利用 “双指针算法” 快速找到两个和为 -a 的数// 细节// 1.不漏// 找到一种结果之后不要停left与right继续靠近继续寻找// 2.去重// 找到一种结果后由于数组有序相同的值紧靠在边上left与right要跳过当前结果对应的相同的值// 找到一种结果后i也要跳过相同值// 3.防止越界//left,right容易越界要确定范围sort(nums.begin(),nums.end());// 1.排序vectorvectorintvv;intnnums.size();for(inti0;in-2;i)// 2.固定一个数a{if(nums[i]0)break;//a0时的优化if(i!0nums[i]nums[i-1])continue;//对固定数a的去重intlefti1,rightn-1;while(leftright){if(left!i1right!n-1nums[left]nums[left-1]nums[right]nums[right1]){//对left和right指向数的去重left;--right;continue;}intsumnums[left]nums[right],target-nums[i];if(sumtarget)--right;elseif(sumtarget)left;else{vv.push_back({nums[left],nums[right],nums[i]});left;--right;//继续寻找}}}returnvv;}};8、四数之和四数之和8.1、题目理解与“三数之和”类似。我们选出的每一个四元组其中每一个数必须来自不同的位置并且这四个数的不同组合都算一个四元组。8.2、原理分析与“三数之和”类似。首先排成升序数组其次从左往右固定数a接着在数a之后的序列中固定数b在数b之后的序列中起始时定义一首一尾下标left, right找到四数之和小于targetleft找到四数之和大于targetright–等于入序列left, --right这是为了不漏去重a要去重b要去重left, right要去重8.3、代码演示classSolution{public:vectorvectorintfourSum(vectorintnums,inttarget){vectorvectorintret;sort(nums.begin(),nums.end());// 排序intnnums.size();//for (int i 0; i n - 3; )for(inti0;in;)//其实这里不需要特殊处理因为超过了操作left, right的循环就进不去了{// 固定afor(intji1;jn;)//这里也一样{// 固定blonglongsum_i_jnums[i]nums[j];intleftj1,rightn-1;while(leftright){// long long防止数据溢出longlongsum_left_rightnums[left]nums[right];if(sum_i_jsum_left_righttarget)left;elseif(sum_i_jsum_left_righttarget)--right;else{// 优化ret.push_back({nums[left--],nums[right--],nums[i],nums[j]});// 对left, right去重while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])--right;}}j;// 对b去重while(jn-2nums[j]nums[j-1])j;}i;// 对a去重while(in-3nums[i]nums[i-1])i;}returnret;}};