WBY's Blog - 双指针
type: channel
link: https://wbyblog.cn/category/%E5%8F%8C%E6%8C%87%E9%92%88/
items: 1658. 将 x 减到 0 的最小操作数
items: 524. 通过删除字母匹配到字典里最长单词
items: 680. 验证回文串 II
items: 633. 平方数之和
items: 142. 环形链表 II
items: 88. 合并两个有序数组

1658. 将 x 减到 0 的最小操作数
type: item
date: 2025-10-22T22:13:29+08:00
description: 题目链接：https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/description/我的思路典型的双指针/滑动窗口类型题目，想到初始化左右两个指针$l=0, r=n-1$，$n$为所给数组的长度，因为我们要找的是最小操作数，那么在判断左右两边到底减哪个时，采用贪心策略，选更大的那一个，就能让$x$减的更快，更快到0，有几种情况：$nums[l]>nums[r]$:$nums[l]\leq x$: 说明此时$nums[l]$可以作为一个操作数，$x-nums[l]$，同时操作数$ans+1$，左指针右移$l+1$$nums[l]>x\geq nums[r]$：则$x-nums[r]$，同样$ans+1$，右指针左移$r-1$$nums[r]>x$：说明中断了，不再满足题目中的条件，直接break$nums[l]\leq nums[r]$:$nums[r]\leq x$：$x-nums[r], ans+1, r-1$$nums[r]>x\geq nums[l]$：$x-nums[l], ans+1, l + 1$$nums[l]>x$：break初始化的$ans=0$，循环条件为$l\leq r,x>0$，当循环跳出后，如果$x\neq0$，则返回-1，反之返回$ans$纠正这个思路看上去很正确，但实际上考虑得并不周全。采用“从两端贪心减x”的策略，这是一种局部决策法。贪心策略失败的根本原因在于：每次“取较大的一端”并不能保证最终组合的和恰好为 x；局部选择（谁大取谁）可能导致后续无解；问题的全局约束是前缀+后缀的组合，而不是连续的减法过程；直观来看，比如下面这个步骤：步骤可选两端贪心选择实际后果1左=9500, 右=9400取左9500看似很好，x减少很多2左=8500, 右=9200取右9200x再减一大块………余下 x=610，后面全是大于610的数，再也无法取到刚好为0贪心能保证局部最优解，但可能会因此掠过全局最优解的进入条件，使得解法陷入到一个死局，本来左边的数一直可以减下去使得$x$最终减到0，尽管这样操作数会变多，但能够实现最终的目的，贪心时可能右边会减掉一个很大的数，导致左边无法再进入后续解中，看似找到了最优实则掉进了陷阱，因此需要用“滑动窗口”或“前缀和”在整个数组范围内找到最优区间，而不能局部决策采用逆向思维，正难则反，题目中说要移除$nums$最左边或最右边的元素，那么剩下的元素是什么呢？其实是$nums$的一个连续子数组，因为左右两边去除的元素之和为$x$，那么剩下的这个子数组中的元素和就应该为$\mathrm{sum}(nums)-x$，那么问题就转化为了我们要找到和为这个数的一个最长子数组（去掉两边的元素数最少，那么中间剩下的要最长，因此是最长子数组）初始化$l=0,target=\mathrm{sum}(nums)-x,ans=-1$，如果$target<0$，那么说明$nums$的所有元素还不够$x$来减的，直接返回-1，接着用enumerate枚举$nums$中的$r,y$，定义一个中间变量$s$，初始化为0，每次枚举时$s+y$，当$s>target$时，说明当前$[l,r]$包含了我们所要的子数组，此时移动左指针缩短窗口（用while循环来实现判断），当$s=target$时，记录下此时的窗口长度，和之前的相比，如果这个长度更大，就更新$ans$，最终返回$n-ans$，因为我们实际要求的还是两边元素的减少个数，因此要做个减法反思为什么$ans$要初始化为-1呢，因为有可能我们要把所有的元素都用上，即这个子数组的长度为0，如果初始化为0，那么我们无法判断是否真正存在符合要求的子数组，在不符合的情况下我们应该返回-1结果时间复杂度：$O(N)$空间复杂度：$O(1)$已是最优解

524. 通过删除字母匹配到字典里最长单词
type: item
date: 2025-04-20T11:47:00+08:00
description: 题目链接：https://leetcode.cn/problems/longest-word-in-dictionary-through-deleting/description/我的思路也是一开始就想到了用双指针，并且根据指导书中写的，这道题是归并两个有序数组的变式，那自然想到一个指针p放在字符串s，一个指针q放在单词word中，依次遍历。思路为：初始化一个结果变量ans=’’以及last_p=len(s)用于判断实现“字母序最小”的要求（比如s="abce", dictionary=["abe","abc"]时应该输出abc而非abe，一开始理解的是c在s中更靠前，所以abc是字母序更小的单词）首先固定q，p移动，判断word[q]是否等于s[p]，如果相等，则p,q同时右移1位，如果不相等，则只移动p，重复该步骤直到遍历完word，即q==len(word)-1，结束该单词的循环，判断len(word)是否>len(ans)，同时判断此时p值是否小于last_p，如果小于，意味着这个答案在s中的次序更靠前，更小，满足题意在同时满足上面三个条件的情况下，则将word赋值给ans，并将p,q指针都放回到0位置，准备开始检查下一个单词这样尽管能跑通，但是犯了一个错误，又是没有get到题目意思，同时被abce这个测试案例给迷惑住了。题目中所指的“字母序最小”的正确意思应该是c比e在26个字母中更靠前，所以应该输出abc，而不是判断字母在s中的位置前后，比如s="bab", dictionary=["ba","ab","a","b"]，应该输出ab而不是ba，因为ab的顺序比ba更”正“，意味着次序更小纠正正确理解题意后可以发现，我们其实压根不需要last_p这个变量，只要判断word和ans哪个更小就好，python中可以实现这样的比较需要判断word和ans的大小的情况只出现在当word和当前ans长度一致时，因此可以把上面几个条件写成一条：if q == len(word) and (len(word) > len(ans) or (len(word) == len(ans) and word < ans))，当该条件为True时，就将word赋值给ans反思字符串也是可以比较大小的，充分用好这一点可以实现题意中的“返回字母序最小”的序列，比如‘abc’<’abe’，返回为True，能够直接判断结果263ms 48.04%, 19.07MB 96.08%

680. 验证回文串 II
type: item
date: 2025-04-15T19:22:00+08:00
description: 题目链接：https://leetcode.cn/problems/valid-palindrome-ii/description/我的思路在这道题上卡了巨久，虽然只是一道标记为简单级别的题，但评论也说了，能比得上中等。亲身尝试后发现确实如此，有很多坑在里面，顺利解答出来也需要一些巧思。我一开始的思路：想到了用双指针，但不知道该从何下手，一开始走入了一个误区（可能是受之前题目的影响，没有仔细看清楚题意），就是尝试修改原字符串，把不一样的赋值成一样的，然后再继续做判断，但是忽略了题目中的要求：最多可以删除一个字符，因此还是要尝试其他的办法想了一下后的思路是：找到那个不对称的位置，然后尝试把这个元素去掉，再判断生下来的字符串是否满足回文，想到了会有一些特殊情况，比如是要去掉左边的元素（例如cd…d，此时应该删掉左边的c），还是去掉右边的元素（例如c…cd，此时应该删掉右边的d），同时还可能只有三个元素（例如abc，或者aba），最多允许删除一个元素……于是就开始了尝试枚举考虑所有可能的特殊情况，删除左边还是右边元素的条件是判断s[left]和s[right]与他们相邻元素是否相同：当出现s[left]≠s[right]的情况时，error+=1，并开始进入如下的条件判断：如果s[right]=s[left+1]，对应上面的cd…d情况，则要把左边的c删掉，取新的片段为s=s[:left]+s[left+1:]如果s[left]=s[right-1]，对应上面的c…cd情况，要把右边的d删掉，取新的片段为s=s[:right]+s[right+1:]如果error>1，则break，返回False如果right-left=1，则说明到了序列的中间，比如abcdba，中间的cd不一样，但可以删掉其中一个使得字符串回文，因此仍返回True执行完上面的条件判断后，如果right==left，说明序列长度为奇数，到了中间值了，或者right-left=1，说明序列长度为偶数，也到了中间了，能执行到这里的话，也返回True，执行完上面所有语句后，将指针进行移动，left-=1, right+=1于是乎，得到了一段屎山代码，又长又臭，以为用了双指针法，但其实还是在做切片，不管能不能通过测试，都能预想到肯定会耗时很长和占用很大内存。这种办法卡在了案例cbbcc，aabdeenddbaagbddeedbaa，和一段很长的字符串纠正把while的循环条件设置为left≤right，这是这种算法题中的常见做法，不要再写True了充分利用好索引的作用，回文的本质就是把字符串倒序还能跟原字符串一致，那可以充分利用这个条件，用or来连接删左或删右的情况，一条代码就可以解决，当遇到两元素不一致的情况时，执行判断s[left+1:right+1] == s[right:left:-1] or s[left:right] == s[right-1:left-1:-1] or s[left:right] == s[right-1::-1]，其中要特别注意s[5:-1:-1]这样的情况是无法得到有效返回的，当left为0时，left-1为-1，不能作为索引来进行切片，这种情况就会报错出现问题，因此还要再另外加上一条判断s[right-1::-1]更简单的做法，写lambda函数，isPalindrome = lambda s: s == s[::-1]，直接判断是否回文，更加简洁明了反思能不产生新的变量（新的列表、字符串之类的）就尽量不要产生，否则会影响内存表现脑子要有明确的概念，保持清醒，对列表的索引、长度要清晰，取片段时才不会犯迷糊节省代码空间，让代码看起来更加简洁漂亮，要充分用好Lambda函数，而不是每次都想到要def来定义新函数执行完判断语句，不要忘记移动指针，否则会进入死循环，不要顾此失彼结果33ms 79.93%, 17.64MB 63.24%

633. 平方数之和
type: item
date: 2025-04-08T12:52:00+08:00
description: 题目链接：https://leetcode.cn/problems/sum-of-square-numbers/description/我的思路知道要用双指针法，但也还是被题目给吓到了，给的c的范围是0到2的31次方-1，感觉从0开始遍历的话复杂度太高了。一开始想着遍历范围是从0到c/2，但感觉这样还是太大。也想过范围为0到根号c，但以为leetcode无法引入其他的库来执行均方根操作，所以一直卡在这，遂去看题解了。纠正枚举法：枚举a=0,1,2,…，把式子变成$b=\sqrt{(c-a^2)}$，只要b是整数的话，就返回True，但a能一直枚举下去吗？不可以，如果枚举到$2a^2>c$的话，仍没有找到合适的b，就停止，证明：此时$a^2>c-a^2$，假如继续枚举能找到符合等式的a和b，比如a=5, b=3，那么之前在枚举到a=3时，也能发现a=3, b=5符合等式，矛盾。所以当枚举到$2a^2>c$时，后面不可能找到符合等式的a和b。双指针法：同样也需要明确指针的活动范围，应该是0到$int(\sqrt c)$，把左指针放到0，右指针放到$int(\sqrt c)$，然后求两指针的平方和，如果数值小于c，则把左指针右移，反之把右指针左移反思Leetcode里也是可以引入一些常用库的，比如math，实现求平方根的操作isqrt函数：能将sqrt的值转化为整数，向下求整显然指针法的耗时会比枚举法要少很多，因此在解决此类问题时不应该一股脑栽进笨方法中开始遍历枚举，而是要想一想是否能有其他更优化的办法结果枚举法：92ms, 28.96%; 17.5MB, 69.68%双指针法：63ms, 64.85%; 17.45MB, 85.4%

142. 环形链表 II
type: item
date: 2025-04-06T16:19:00+08:00
description: 题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/我的思路第一次遇到这种题，有点被吓到了，不知道什么是链表，被题目里的定义和复杂的描述给唬住了，一直在纠结给出代码中的ListNode类的定义是什么，读懂题意花了很长时间，没有自己的解答思路纠正理解题意：给的链表其实就是有序的列表，然后这道题里在有序的列表基础上形成了环，那么这种结构就会涉及到几个新的元素：链表起点（叫做头，head）、环的起点（题目里pos给出了环起点的索引），自己一开始感到奇怪，明明给了链表的环起点pos，为什么还要判断是否有环以及求环的起点索引？因为题目里很明确地说了，pos变量不会作为参数进行传递，是评测系统内部的一个参数，表示链表尾链接到链表中的位置，只是为了标识链表的实际情况，因此这只是一个让我们知道这个链表有没有环结构的一个标志，对我们的实际问题求解不会有什么影响和帮助，那么我们要怎么判断这个链表是否存在环呢？题目里也很明确地告诉我们了，只要链表中后续还有节点，就可以一直使用.next指针到达，同时如果这个过程能够一直循环下去的话，就说明链表中存在环（很合理，不然next就是None了）我们要做什么？目标就是找到链表环结构的起点，按照题目的意思来说，也就是链表尾被连接回到了链表中的哪个位置，返回对应的索引值正确思路采用快慢双指针的思路，一个慢（速度为1，即1个单位时间走1个节点），一个快（速度为2，即1个单位时间走2个节点）为什么这么做？因为我们要确定的是环的入口位置，那单纯只靠一个指针来走不太可能能确定这个位置在哪，所以我们要引入两个，且两个指针的速度要不一样，这样他们之间在相同时间内走过的距离会存在一个差值，同时因为环结构的存在，二者会在某一个时刻相遇，那么他们走过的路程、差值、相遇时刻与环的起点位置、环的长度这几个量之间或许存在某种关系，这是我们可以尝试的一个思路。其实或许这个做法在算法题解中是常用的，只是自己第一次接触不太知道，会这么想，后面熟悉后可以举一反三直接用这样的办法，这就是一个“没有为什么”的解法。这种算法叫Floyd判圈算法Floyd判圈算法用于高效检测序列（如链表）中是否存在环（循环）。其核心解决思路是使用快慢双指针（龟兔赛跑），慢指针每次移动一步，快指针移动两步。如果存在环，两指针必定会相遇；如果快指针到达终点，则无环。此算法能以常数空间复杂度(O(1))和线性时间复杂度(O(n))解决问题，效果极佳。此外，它还能用于寻找环的起点：在两指针相遇后，将其中一个指针重置回起点，然后两指针同速前进，再次相遇点即为环的入口。给我们一个如上的链表，我们先假设几个重要的量，从链表头到环起点的距离为z，慢指针刚走到环入口时，快指针已经又走过了环的x个节点，y表示从此时快指针走到环起点还需要走几步，那么环的长度为x+y（注意，这里的“距离”都是包括了起点和终点的，并且指的是有这两段之间有几个节点），慢指针slow速度为1，快指针fast速度为2，我们关键是要找出z为多少首先把快慢指针都放到头部，设为起点，slow = head, fast = head，让他们开始往下走往下走的过程可以用一个while来实现，但在while的开始需要加一个判断语句，如果这个目前元素为空（以fast为例，条件语句为fast == None或者not fast），或者没有下一个元素了（not fast.next），这两种情况都说明这个链表是没有环结构的，自然也不存在所谓的环起点，返回None即可，程序结束如果还能继续往下走，那就继续执行后面的判断，slow每次走1步，所以slow = slow.next，fast每次走2步，所以fast = fast.next.next我们第一个比较好“拿捏”的地方是slow刚好到了环入口时，即在不断重复3的情况下，当slow刚好要进环时，此时fast可能已经在环中走了k圈，k为正整数，那么fast一共走过的路程为z+x+k(x+y)，此时slow走过的总路程为z，因为fast的速度为slow的两倍，所以fast走过的路程也应为slow的两倍，因此有z+x+k(x+y)=2z，计算得出z=x+k(x+y)，于是我们就得到了我们想要的关键信息z的一个表达式，因此可以得到：让两个指针继续往下走，此时慢指针已经入环了，那么可以肯定在未来某个时刻，慢指针和快指针一定会在环的某个位置相遇，而且我们可以得出，这个位置是在入环后再走y个节点的位置，推导：慢指针刚入环时，快指针距离环入口还需要走y步，那么意味着经过时间y/2，快指针便会回到环入口，此时慢指针走过了y/2*1=y/2个节点，二者继续往下走，当再经过y/2时间时，此时慢指针和快指针刚好都走到了离起点y…

88. 合并两个有序数组
type: item
date: 2025-04-03T11:42:00+08:00
description: 我的思路直接尝试赋新值给nums1=nums1[:m]+nums2，但在Leetcode的运行环境中，这样的办法行不通，只是重新绑定了一个新的列表对象，原先的nums1并没有被改变，在测试的时候后台会检查原先的nums1是否有被修改，因此这种办法是行不通的，需要在原数组上一个个修改数值才行纠正还是需要用双指针的思路，判断值，然后把值填进表中初始化三个指针，分别定位在nums1（短）、nums2和nums1（长）的最后一个元素，对应的索引值分别为m-1, n-1, m+n-1，接下来依次开始判断nums1（短）和nums2的元素大小，把更大的那个放到nums1（长）的后面，这也是为什么要有第三个指针的原因，因为我们需要修改的是原始nums1例子：nums1 = [1,2,3,0,0,0,0], m = 3, nums2 = [2,4,5,7], n = 4思路：初始化三个指针的值分别为p = 2, q = 3, pos = 6，从左右边开始：判断nums1[2]和nums2[3]的大小，7>3，所以把7放到nums1[6]，此时已经将nums2[3]的这个元素用掉了，所以要把nums2对应的指针往左边移一位，q -= 1，变成2，p的值不变，因为这个元素还没有被安排掉，同时nums1[6]已经安排了数字进来，所以第三个指针也要往左移，pos -= 1判断nums1[2]和nums2[2]的大小，5>3，所以把5放到nums1[5]，重复上面的步骤判断nums1[2]和nums2[0]的大小，3>2，所以把3放到nums1[3]，然后p -= 1，p变为1，q仍为0，pos变为2判断nums1[1]和nums2[0]的大小，两个数值相等，放哪一个都可以，默认把nums2的这个元素放过去，所以把2放到nums1[2]，然后q -= 1，q变为-1，说明nums2的元素全部放完了，结束反思这题比较好的地方在于，给到的序列已经是按顺序排好了的，都是非递减数列，不需要我们再做排序操作，可以直接按顺序遍历进行比较和放置数值需要比较巧妙处理的一个点是，在大的while循环中条件要设置为q>0，因为可能已经把nums1（短）的元素全部安排完了，但nums2还有元素，需要继续安排。一方面题目给到我们的序列已经是按非递减顺序排好了的，另一方面就算p<0了，根据我们的程序设计，这说明我们已经安排完了nums1（短）的所有元素，每个元素都已经被放置，所以此时原先nums1（短）剩下的这几个位置相当于是没用的，直接再把nums2里剩下的元素按顺序安排过来就好了结果0ms (100%), 17.47MB (78.94%)