【五】【算法分析与设计】双指针的初见

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

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

以长度为 2 的整数数组 [index(1), index(2)] 的形式返回这两个整数的下标 index(1) 和 index(2)。

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

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

示例 1：

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

示例 2：

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

示例 3：

输入：numbers = [-1,0], target = -1 输出：[1,2] 解释：-1 与 0 之和等于目标数 -1 。因此 index(1) = 1, index(2) = 2 。返回 [1, 2] 。

提示：

• 2 <= numbers.length <= 3 * 10(4)

• -1000 <= numbers[i] <= 1000

• numbers 按 非递减顺序 排列

• -1000 <= target <= 1000

• 仅存在一个有效答案

vector<int> twoSum(vector<int>& numbers, int target) {
    int l = 0, r = numbers.size() - 1, sum;
    while (l < r) {
        sum = numbers[l] + numbers[r];
        if (sum == target) break;
        if (sum < target) ++l;
        else --r;
    }
    return vector<int> {l + 1, r + 1};
 }

这段代码是一个实现“两数之和”问题的函数，使用了双指针技巧。它的目标是在一个已排序的数组中找到两个数，使得它们的和等于给定的目标值target。找到后，返回这两个数的索引+1（题目假定索引从1开始而不是从0开始）。

int l = 0, r = numbers.size() - 1, sum;这一行初始化了两个指针，l（左指针）和r（右指针），分别指向数组的开始位置和结束位置。同时，声明了一个sum变量用于存储两个指针所指元素的和。

while (l < r) {这是一个while循环，条件是左指针l小于右指针r。这个条件保证了在数组内部移动指针时不会越界或重叠。

sum = numbers[l] + numbers[r];在循环体内，计算当前左指针和右指针所指向的元素的和。

if (sum == target) break;如果这个和等于目标值target，则跳出循环，因为已经找到满足条件的两个数。

if (sum < target) ++l; else --r;如果这个和小于目标值target，则将左指针向右移动一位（因为数组已排序，这样做可以增加和的值）。否则，将右指针向左移动一位（这样做可以减少和的值）。

return vector {l + 1, r + 1};最后，返回一个新的vector，其中包含满足条件的两个数的索引+1（按照题目要求，索引从1开始计数）。

时间复杂度分析：

这个算法的时间复杂度为O(n)，其中n是数组numbers的长度。因为每个元素最多被访问一次，且左右指针最多移动n次。

空间复杂度分析：

空间复杂度为O(1)，因为使用的额外空间不随输入数据的大小而改变，仅使用了固定大小的空间来存储指针和中间变量。

88. 合并两个有序数组

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

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

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

示例 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 中。

提示：

• nums1.length == m + n

• nums2.length == n

• 0 <= m, n <= 200

• 1 <= m + n <= 200

• -10(9) <= nums1[i], nums2[j] <= 10(9)

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
    int pos = m-- + n-- - 1;
    while (m >= 0 && n >= 0) {
        nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
    }
    while (n >= 0) {
        nums1[pos--] = nums2[n--];
    }
 }

这段代码实现的功能是合并两个已排序的数组nums1和nums2。nums1的大小足以包含nums1和nums2合并后的所有元素，其中m和n分别是nums1和nums2中初始化元素的数量。

int pos = m-- + n-- - 1;这行代码初始化了一个变量pos，它表示合并后数组的最后一个元素的位置。由于数组的索引是从0开始的，所以需要m + n - 1来计算pos的位置。接着，m和n分别减1，为接下来的操作做准备（因为在C++中，数组的索引是从0开始的，而m和n是元素的数量）。此时m和n分别指向原nums1最后一个元素和nums2最后一个元素。

while (m >= 0 && n >= 0) {这个while循环继续执行，直到nums1或nums2中的元素被完全遍历。条件m >= 0 && n >= 0确保了不会访问任何数组的负索引。

nums1[pos--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];在循环体内，通过比较nums1[m]和nums2[n]的大小，决定nums1[pos]的值。这里使用了三元运算符：如果nums1[m]大于nums2[n]，则将nums1[m]赋值给nums1[pos]，否则将nums2[n]赋值给nums1[pos]。无论哪种情况，pos都会递减，指向下一个待填充的位置。同时，被选中的那个数组的索引也会递减，以便于下一次比较。

while (n >= 0) {这个while循环是为了处理nums2中剩余的元素。如果nums1中的所有元素都已经被正确放置，但nums2中还有剩余的元素，这个循环会将它们复制到nums1的相应位置。

nums1[pos--] = nums2[n--];在循环体内，将nums2中剩余的元素依次复制到nums1的正确位置上，同时更新pos和n的值。

没有包含处理nums1剩余元素的循环，因为nums1的剩余元素已经在合适的位置上，不需要移动。

时间复杂度分析：

这个算法的时间复杂度为O(m + n)，其中m是nums1中初始化元素的数量，n是nums2中元素的数量。每个元素只被访问和比较一次。

空间复杂度分析：

空间复杂度为O(1)，因为合并是就地进行的，没有使用额外的存储空间。

142. 环形链表 II

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

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

不允许修改 链表。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

• 链表中节点的数目范围在范围 [0, 10(4)] 内

• -10(5) <= Node.val <= 10(5)

• pos 的值为 -1 或者链表中的一个有效索引

进阶：你是否可以使用 O(1) 空间解决此题？

ListNode *detectCycle(ListNode *head) {
    ListNode *slow = head, *fast = head;
// 判断是否存在环路
    do {
        if (!fast || !fast->next) return nullptr;
        fast = fast->next->next;
        slow = slow->next;
    } while (fast != slow);
// 如果存在，查找环路节点
    fast = head;
    while (fast != slow) {
        slow = slow->next;
        fast = fast->next;
    }
    return fast;
 }

这段代码是用于检测链表中是否存在环，如果存在，返回环的入口节点。这个算法使用了快慢指针的技巧，分为两个主要部分：检测环的存在和找到环的入口。

ListNode *slow = head, *fast = head;首先，声明两个指针slow和fast，都初始化为链表的头节点head。slow每次向前移动一个节点，而fast每次向前移动两个节点。

do { if (!fast || !fast->next) return nullptr;在do-while循环中，首先检查fast指针或者fast->next是否为nullptr。如果是，说明链表没有环，因为在链表有环的情况下，fast指针不会遇到nullptr。

fast = fast->next->next; slow = slow->next; } while (fast != slow);如果链表中没有出现nullptr，则fast指针每次移动两步，slow指针每次移动一步。这个过程一直持续到fast指针和slow指针相遇，相遇说明链表中存在环。

fast = head;当检测到链表中有环后，将fast指针重新指向链表头节点head。

while (fast != slow) { slow = slow->next; fast = fast->next; }然后，让fast指针和slow指针都每次向前移动一个节点，当它们再次相遇时，相遇点就是环的入口节点。

时间复杂度分析：

第一部分（检测环的存在）的时间复杂度为O(N)，其中N是链表中节点的数量。在最坏的情况下，快慢指针会在环的入口相遇，此时快指针已经遍历了整个链表。

第二部分（找到环的入口）的时间复杂度也为O(N)，但实际上这部分的运行次数不会超过链表的长度，因此在实际中这部分的时间消耗通常小于第一部分。

因此，总体时间复杂度为O(N)。

空间复杂度分析：

空间复杂度为O(1)，因为这个算法只使用了固定的几个指针，没有使用额外的存储空间。

76. 最小覆盖子串

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

注意：

• 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

• 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

示例 2：

输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。

示例 3:

输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。

提示：

• (m == s.length)

• (n == t.length)

• 1 <= m, n <= 10(5)

• s 和 t 由英文字母组成

进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？

string minWindow(string S, string T) {
    vector<int> chars(128, 0);
    vector<bool> flag(128, false);
// 先统计T中的字符情况
    for (int i = 0; i < T.size(); ++i) {
        flag[T[i]] = true;
        ++chars[T[i]];
    }
// 移动滑动窗口，不断更改统计数据
    int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;
    for (int r = 0; r < S.size(); ++r) {
        if (flag[S[r]]) {
            if (--chars[S[r]] >= 0) {
                ++cnt;
            }
// 若目前滑动窗口已包含T中全部字符，
 // 则尝试将l右移，在不影响结果的情况下获得最短子字符串
            while (cnt == T.size()) {
                if (r - l + 1 < min_size) {
                    min_l = l;
                    min_size = r - l + 1;
                }
                if (flag[S[l]] && ++chars[S[l]] > 0) {
                    --cnt;
                }
                ++l;
            }
        }
    }
    return min_size > S.size() ? "" : S.substr(min_l, min_size);
 }

vector chars(128, 0); vector flag(128, false);这两行代码初始化了两个大小为128的数组chars和flag。chars用于存储字符串T中各字符出现的次数，而flag标记字符串T中是否包含某个字符（ASCII码范围为0-127）。

for (int i = 0; i < T.size(); ++i) { flag[T[i]] = true; ++chars[T[i]]; }这个循环遍历字符串T，更新T中字符的出现频率，同时标记这些字符在flag数组中。

int cnt = 0, l = 0, min_l = 0, min_size = S.size() + 1;声明和初始化四个变量：cnt用于记录当前窗口中已匹配的T中字符数量，l是窗口的左边界，min_l记录最小窗口的起始位置，min_size记录最小窗口的长度（初始值设为S.size() + 1，保证一开始任何窗口长度都小于min_size）。

for (int r = 0; r < S.size(); ++r) {这个循环通过右指针r遍历字符串S，用来扩展窗口的右边界。

if (flag[S[r]]) {如果当前字符S[r]在T中出现过（通过flag检查），则处理字符。

if (--chars[S[r]] >= 0) { ++cnt; }字符S[r]对应的chars数组减1，如果减1后仍大于等于0，意味着当前字符是T中需要的字符之一，因此cnt加1。

while (cnt == T.size()) {当cnt等于T的长度时，意味着当前窗口已包含T中所有字符。

if (r - l + 1 < min_size) { min_l = l; min_size = r - l + 1; }如果当前窗口的长度小于已知的最小长度min_size，则更新最小窗口的起始位置min_l和长度min_size。

if (flag[S[l]] && ++chars[S[l]] > 0) { --cnt; } ++l;尝试缩小窗口的左边界，即右移左指针l。如果移除的字符是T中的字符（flag[S[l]]为true），且chars[S[l]]在增加1后大于0，意味着移除了一个必需的字符，因此cnt减1。

return min_size > S.size() ? "" : S.substr(min_l, min_size);如果min_size大于S的长度，说明没有找到符合条件的窗口，返回空字符串；否则，返回最小窗口子串。

时间复杂度分析：

时间复杂度为O(N)，其中N是字符串S的长度。虽然有一个嵌套的while循环，但每个字符在S中最多被访问两次（一次由右指针扩展窗口，一次由左指针缩小窗口），因此总的时间复杂度仍为O(N)。

空间复杂度分析：

空间复杂度为O(1)，因为chars和flag数组的大小固定为128，与输入字符串的大小无关。

结尾

最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。

同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。

谢谢您的支持，期待与您在下一篇文章中再次相遇！