玩转双指针

一、算法解释

双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。

若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的区域即为当前的窗口），经常用于区间搜索。

若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。

二、两数之和

2.1、两数之和 II - 输入有序数组

2.1.1、题目描述

167. 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

2.1.2、输入输出示例

示例1：
输入： numbers = [2, 7, 11, 15], target = 9
输出： [1, 2]
解释： 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

示例2：
输入： numbers = [2, 3, 4], target = 6
输出： [1, 3]
解释： 2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3] 。

示例3：
输入： numbers = [-1, 0], target = -1
输出： [1, 2]
解释： -1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。

2.1.3、题解

三、数组合并

3.1、合并两个有序数组

3.1.1、题目描述

88. 合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意： 最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

3.1.2、输入输出示例

示例1：
输入： nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
输出： [1, 2, 2, 3, 5, 6]
解释： 需要合并 [1, 2, 3] 和 [2, 5, 6] 。 合并结果是 [1, 2, 2, 3, 5, 6] ，
    其中斜体加粗标注的为 nums1 中的元素。

示例2：
输入： nums1 = [1], m = 1, nums2 = [], n = 0
输出： [1]
解释： 需要合并 [1] 和 [] 。
    合并结果是 [1] 。

示例3：
输入： nums1 = [0], m = 0, nums2 = [1], n = 1
输出： [1]
解释： 需要合并的数组是 [] 和 [1] 。
    合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

3.1.3、题解

四、快慢指针

4.1、环形链表 II

4.1.1、题目描述

142. 环形链表 II

给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置 （索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

不允许修改 链表。

4.1.2、输入输出示例

示例1：

输入： head = [3, 2, 0, -4], pos = 1
输出： 返回索引为 1 的链表节点
解释： 链表中有一个环，其尾部连接到第二个节点。

示例2：

输入： head = [1, 2], pos = 0
输出： 返回索引为 0 的链表节点
解释： 链表中有一个环，其尾部连接到第一个节点。

示例3：

输入： head = [1], pos = -1
输出： 返回 null
解释： 链表中没有环。

4.1.3、题解

五、滑动窗口

5.1、最小覆盖子串

5.1.1、题目描述

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

5.1.2、输入输出示例

示例1：
输入： s = “ADOBECODEBANC”, t = “ABC”
输出： “BANC”

示例2：
输入： s = “a”, t = “a”
输出： “a”

示例3：
输入： s = “a”, t = “aa”
输出： “”
解释： t 中两个字符 ‘a’ 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。

5.1.3、题解

六、练习

6.1、基础难度

6.1.1、平方数之和

6.1.1.1、题目描述

633. 平方数之和

给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

6.1.1.2、输入输出示例

示例1：
输入： c = 5
输出： true
解释： 1 * 1 + 2 * 2 = 5

示例2：
输入： c = 3
输出： false

6.1.1.3、题解

6.1.2、验证回文字符串 Ⅱ

6.1.2.1、题目描述

680. 验证回文字符串 Ⅱ

给定一个非空字符串 s，最多删除一个字符。判断是否能成为回文字符串。

6.1.2.2、输入输出示例

示例1：
输入： s = “aba”
输出： true

示例2：
输入： s = “abca”
输出： true
解释： 你可以删除c字符。

示例3：
输入： s = “abc”
输出： false

6.1.2.3、题解

6.1.3、通过删除字母匹配到字典里最长单词

6.1.3.1、题目描述

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

给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

6.1.3.2、输入输出示例

示例1：
输入： s = “abpcplea”, dictionary = [“ale”, “apple”, “monkey”, “plea”]
输出： “apple”

示例2：
输入： s = “abpcplea”, dictionary = [“a”, “b”, “c”]
输出： “a”

6.1.3.3、题解

6.2、进阶难度

6.2.1、至多包含K个不同字符的最长子串

6.2.1.1、题目描述

340. 至多包含 K 个不同字符的最长子串

给定一个字符串 s ，找出 至多 包含 k 个不同字符的最长子串 T。

6.2.1.2、输入输出示例

示例1：
输入： s = “eceba”, k = 2
输出： 3
解释： 则 T 为 “ece”，所以长度为 3。

示例2：
输入： s = “aa”, k = 1
输出： 2
解释： 则 T 为 “aa”，所以长度为 2。

6.2.1.3、题解