刷题笔记二：双指针算法

用这种发帖的方式来激励自己做总结，从而更好的掌握知识点。建议初学者都像这样一个知识点一个知识点的刷题，效率会更高。题目都是来自leetcode, 如果有啥没概括到的，或者写错的地方，还请大佬们指正！

核心：双指针主要用于遍历数组，两个指针指向不同的元素，协同完成任务。在某些情况下也可用多指针来解答。
常用的情况有用于搜索，两个指针指向同一数组，但是遍历方向相反，这种情况下的数组通常是排好序的（如指1跟10，继续往下指2跟9）。
用于区间搜索的话，可以用滑动窗口，即两个指针指向同一数组，但是遍历方向相同且不会交叉（如1到5，2到6这样往下滑）。

涉及问题：
1.        Two sum
1)        Lc 167: Two Sum II - Input Array Is Sorted： 在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。
题解：因为数组是排好序的，则可以用相反方向的双指针来进行搜索，初始分别指向最大和最小的数，向中间数遍历。若两个指针指向的元素之和等于我们的目标和，则拿到了我们要的结果。若两个指针指向的元素之和小于目标，则往右移动左指针使和变大。反之，若两个指针指向的元素之和大于目标，则往左移动右指针使和变小，直到找到我们要的值。
2.        归并两个有序数组
1)        Lc 88: Merge Sorted Array: 给定两个有序数组，把两个数组合并为一个。
题解：因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。 因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。这里需要注意，如果 nums1 的数字已经复制完，不要忘记把 nums2 的数字继续复制;如果 nums2 的数字已经复制完，剩余 nums1 的数字不需要改变，因为它们已经被排好序。
3.        快慢指针
1)        Lc 142. Linked List Cycle II： 给定一个链表，如果有环路，找出环路的开始点。
题解：给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路; 如果 fast 可以无限走下去，那么说明一定有环路，且一定存 在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并 让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。
4.        滑动窗口
1)        76. Minimum Window Substring: 给定两个字符串 S 和 T ，求 S 中包含 T 所有字符的最短连续子字符串的长度，同时要求时间 复杂度不得超过 O(n)。
题解：使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在 r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移 动 l 指针，且 l 只会从左到右移动一次，因此总时间复杂度仍然是 O(n)。

练习题：
基础：633 Sum of Square Numbers (Easy)， 680 Valid Palindrome II (Easy)， 524 Longest Word in Dictionary through Deleting (Medium).
进阶：340 Longest Substring with At Most K Distinct Characters (Hard).

小伙伴记得点赞收藏，当然收藏了也别让笔记吃灰，记得交作业哦，有问题🉑️留言咱们一起讨论！

妈耶 支持博主！请继续更！

smol cass 发表于 2022-6-6 13:16
妈耶 支持博主！请继续更！

木有问题，求加米～～～哈哈哈