524. 通过删除字母匹配到字典里最长单词

题目链接：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赋值给an

双指针 · 04-20

680. 验证回文串 II

题目链接：https://leetcode.cn/problems/valid-palindrome-ii/description/我的思路在这道题上卡了巨久，虽然只是一道标记为简单级别的题，但评论也说了，能比得上中等。亲身尝试后发现确实如此，有很多坑在里面，顺利解答出来也需要一些巧思。我一开始的思路：想到了用双指针，但不知道该从何下手，一开始走入了一个误区（可能是受之前题目的影响，没有仔细看清楚题意），就是尝试修改原字符串，把不一样的赋值成一样的，然后再继续做判断，但是忽略了题目中的要求：最多可以删除一个字符，因此还是要尝试其他的办法想了一下后的思路是：找到那个不对称的位置，然后尝试把这个元素去掉，再判断生下来的字符串是否满足回文，想到了会有一些特殊情况，比如是要去掉左边的元素（例如cd…d，此时应该删掉左边的c），还是去掉右边的元素（例如c…cd，此时应该删掉右边的d），同时还可能只有三个元素（例如abc，或者aba），最多允许删除一个元素……于是就开始了尝试枚举考虑所有可能的特殊情况，删除左边还是右边元素的条件是判断s[left]和s[right]与他们相邻元素是否相同：当出现s

双指针 · 04-15

633. 平方数之和

题目链接：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)

双指针 · 04-08

142. 环形链表 II

题目链接：https://leetcode.cn/problems/linked-list-cycle-ii/description/我的思路第一次遇到这种题，有点被吓到了，不知道什么是链表，被题目里的定义和复杂的描述给唬住了，一直在纠结给出代码中的ListNode类的定义是什么，读懂题意花了很长时间，没有自己的解答思路纠正理解题意：给的链表其实就是有序的列表，然后这道题里在有序的列表基础上形成了环，那么这种结构就会涉及到几个新的元素：链表起点（叫做头，head）、环的起点（题目里pos给出了环起点的索引），自己一开始感到奇怪，明明给了链表的环起点pos，为什么还要判断是否有环以及求环的起点索引？因为题目里很明确地说了，pos变量不会作为参数进行传递，是评测系统内部的一个参数，表示链表尾链接到链表中的位置，只是为了标识链表的实际情况，因此这只是一个让我们知道这个链表有没有环结构的一个标志，对我们的实际问题求解不会有什么影响和帮助，那么我们要怎么判断这个链表是否存在环呢？题目里也很明确地告诉我们了，只要链表中后续还有节点，就可以一直使用.next指针到达，同时如果这个过程能够一直循环下去

双指针 · 04-06

88. 合并两个有序数组

我的思路直接尝试赋新值给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]的这个元素用掉了，所以要把num

双指针 · 04-03