目录总结这种题目的通用“模板”二、 核心思路快慢指针法二、 这个思路是如何推导出来的思维演变过程阶段 1暴力直觉不符合要求的想法阶段 2“空间换时间”的假想寻找灵感阶段 3“空间融合”与指针的诞生破局点阶段 4为什么是“交换”而不是直接覆盖class Solution { public void duplicateZeros(int[] arr) { int i 0; int top 1; for(;toparr.length;i){ if(arr[i] ! 0){ top; }else{ top 2; } } for(int j arr.length-1;i! 0;i--){ if(arr[i] 0top arr.length1){ 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 了。但是如果是交换Swapcur找回来的非零元素放到了dest的位置而dest原本指向的0则被扔到了cur扫描过后的废弃区域。这样不仅完成了非零元素的搬运还顺手把 0 像滚雪球一样推到了数组的尾部