专题一双指针

专题一双指针1.移动0数组分块给定一个数组nums编写一个函数将所有0移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下 原地 对数组进行操作。cur扫描数组。dest分界扫描过的前非0元素与后0元素。分割形成的原理cur :遇0cur非0des 交换 cur拓展来看区域数据的划分。2.双0复写从后写入给你一个长度固定的整数数组arr请你将该数组中出现的每个零都复写一遍并将其余的元素向右平移。注意请不要在超过该数组长度的位置写入元素。请对输入的数组就地进行上述修改不要从函数返回任何东西。1.cur扫描 实现dest、cur的定位cur 0,dest -1;[cur]非零 dest 若destsize-1break; cur[cur]为零 dest2 若destsize-1break; cur;2.特殊情况处理(des越界)[size-1] 0; cur--; dest - 2;为什么会有特殊情况第二步的逻辑假设与第一步的dest2相关联。3.从后往前复写cur至最后一个要写的数dest从后往前[cur]为0 [dest]为0 dest-- [dest]为0 dest-- cur--[cur]非零 交换 dest-- cur--反思下标2就可能越界像指针-next-next一样 可能在中途出现空指针。3.数组元素循环判断 快乐数尾循环编写一个算法来判断一个数n是不是快乐数。「快乐数」定义为对于一个正整数每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1也可能是无限循环但始终变不到 1。如果这个过程结果为1那么这个数就是快乐数。如果n是快乐数就返回true不是则返回false。快慢指针体现于 每次取各个位的平方和的次数若n 19那么s 1^2 9^2 82; f 8^2 2^2; 此后f按照自身数来进行两步 s按照自身数来进行一步。 ↓//为什么不能按照s来呢 答案f的相对位移逐增。题眼1的循环看待快慢指针的定义4.数组水桶问题给定一个长度为n的整数数组height。有n条垂线第i条线的两个端点是(i, 0)和(i, height[i])。找出其中的两条线使得它们与x轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。说明你不能倾斜容器。左右聚拢的依据(本质为单调性的使用)双指针向内聚拢 更新最大值。5.有效三角形个数使用sort快排减少三角形决断次数 若a b c 那么满足abc即可cur2l r①a b c sum right - left;,right-- //中间部分全大于②a b c left; //left向中间聚拢找可能存在的反思主要利用单调性来简化三角形次数的判断练习要求打草画清晰图 结构化 了解双指针的内涵递增数组元素 查找 定和值购物车内的商品价格按照升序记录于数组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]6.三数和前言基于两数和进行。给你一个整数数组nums判断是否存在三元组[nums[i], nums[j], nums[k]]满足i ! j、i ! k且j ! k同时还满足nums[i] nums[j] nums[k] 0。请你返回所有和为0且不重复的三元组。注意答案中不可以包含重复的三元组。固定 i 在i的左侧利用双指针来寻找与-nums[i]相等的和值 。去重内部去重 外部去重