力扣算法练练练1——双指针
目录
总结：这种题目的通用“模板”
二、 核心思路：快慢指针法
二、 这个思路是如何推导出来的？（思维演变过程）
阶段 1：暴力直觉（不符合要求的想法）
阶段 2：“空间换时间”的假想（寻找灵感）
阶段 3：“空间融合”与指针的诞生（破局点）
阶段 4：为什么是“交换”而不是直接覆盖？
class Solution { public void duplicateZeros(int[] arr) { int i = 0; int top = 1; for(;top<arr.length;i++){ if(arr[i] != 0){ top++; }else{ top += 2; } } for(int j = arr.length-1;i!= 0;i--){ if(arr[i] == 0&&top == arr.length+1){ arr[j] = 0; j--; }else if(arr[i] == 0){ arr[j]= arr[j-1] =0; j -=2; }else{ arr[j] = arr[i]; j--; } } } }总结：这种题目的通用“模板”
当你看到题目要求：
原地（In-place）修改。
涉及到元素的增加、复写或大规模平移。
数组长度固定或要求删除元素。
你的大脑应该立刻跳出这个条件反射：> “我能不能先算一下结果数组长什么样，然后从后往前填数据？”
这种“后序填空法”能完美避开数据覆盖的陷阱，是处理数组平移类问题的万能钥匙。
二、 核心思路：快慢指针法
基于上面的推导，我们得到了时间复杂度极佳且空间复杂度为 $O(1)$ 的最优解法。
定义指针：* 设定一个慢指针
slow，每次走一步（即进行一次各位平方和计算）。设定一个快指针
fast，每次走两步（即连续进行两次各位平方和计算）。
开始追击：
让
slow和fast同时从起点 $n$ 出发，不断循环推进。
判断终局：
如果这条路径没有环，
fast会先到达 1。只要fast或fast的下一步是 1，就是快乐数。如果这条路径有环，由于
fast比slow跑得快，它们总有一天会在环内的某个数字上相遇（即slow == fast）。一旦相遇，我们就看相遇时的数字是不是 1。如果是 1，说明在 1 这个终点处循环（1 的平方和还是 1），是快乐数；如果不是 1，说明在其他数字组成的死胡同里死循环了，不是快乐数。
二、 这个思路是如何推导出来的？（思维演变过程）
在没有任何提示的情况下，面对“原地修改”和“保持相对顺序”这两个苛刻条件，我们可以经历以下三个思考阶段：
阶段 1：暴力直觉（不符合要求的想法）
最容易想到的办法是：每次遇到 0，就把后面的所有元素往前挪一步，把 0 挤到最后。
推翻：数组元素的插入和删除（或者说整体平移）时间复杂度是 $O(N)$。如果数组里有很多 0，整体复杂度会飙升到 $O(N^2)$，效率太低。
阶段 2：“空间换时间”的假想（寻找灵感）
如果题目没有“原地操作”的限制，允许我们新开一个数组，我们会怎么做？
非常简单：准备一个空数组，遍历原数组，看到非 0 的数字就按顺序塞进新数组里。遍历完后，新数组剩下的空位全部填 0 即可。
这个逻辑极其高效，时间复杂度只需 $O(N)$。
阶段 3：“空间融合”与指针的诞生（破局点）
核心顿悟：能不能在原数组的“前半部分”模拟那个“新数组”？
既然 0 最终都要去后面，而我们只关心非零元素的相对顺序，那我们完全可以把原数组的头部当成那个“新数组”来用。
这就是两个指针诞生的时刻：
我们需要一个指针（
cur）去原数组里“进货”（找非零元素）。我们需要另一个指针（
dest）在原数组的头部负责“摆货”（记录非零元素该放的位置）。
阶段 4：为什么是“交换”而不是直接覆盖？
如果我们直接把
nums[cur]的值赋给nums[dest]，会导致原有的 0 被覆盖掉，后续我们就不知道该在哪里补 0 了。但是，如果是交换（Swap），
cur找回来的非零元素放到了dest的位置，而dest原本指向的0则被扔到了cur扫描过后的废弃区域。这样不仅完成了非零元素的搬运，还顺手把 0 像滚雪球一样推到了数组的尾部！