LeetCode刷题笔记(二): 双指针

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

一、Two Sum

• 题目：两数之和 II - 输入有序数组
  给你一个下标从1开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

  解答：

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

  提示：利用非递减数列的性质。

二、归并两个有序数组

• 题目：合并两个有序数组
  给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
  请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

  解答：

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

  提示：简单题。

三、滑动窗口

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

  解答：

  class Solution {
  public:
      string minWindow(string s, string t) {
          vector<bool> valid(123);
          vector<int> frequence(123);
          for (char c : t) {
              valid[c] = true;
              frequence[c]++;
          }
          int min_length = -1;
          int min_r = 0;
          int l = 0, r = 0;
          int count = accumulate(valid.begin(), valid.end(), 0);
          while (l < s.length()) {
              if (valid[s[l]]) {
                  frequence[s[l]]--;
                  if (frequence[s[l]] == 0) count--;
                  if (count == 0) {
                      while (!valid[s[r]] || frequence[s[r]] < 0) {
                          if (frequence[s[r]] < 0) 
                              frequence[s[r]]++;
                          r++;
                      }
                      if (min_length == -1 || min_length > l - r + 1) {
                          min_length = l - r + 1;
                          min_r = r;
                      }
                  }
              }
              l++;
          }
  
          return min_length == -1 ? "" : s.substr(min_r, min_length);
      }
  };

  提示：需要存储某些信息来方便处理。

四、快慢指针

• 题目：环形链表 II

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

  解答：

  // Definition for singly-linked list.
  // struct ListNode {
  //     int val;
  //     ListNode *next;
  //     ListNode(int x) : val(x), next(nullptr) {}
  // };
  
  class Solution {
  public:
      ListNode *detectCycle(ListNode *head) {
          ListNode *slow = head;
          ListNode *fast = head;
          bool has_cycle = true;
          while (fast != slow || has_cycle) {
              if (fast == nullptr || fast->next == nullptr) {
                  return nullptr;
              }
              fast = fast->next->next;
              slow = slow->next;
              has_cycle = false;
          }
          fast = head;
          while (fast != slow) {
              fast = fast->next;
              slow = slow->next;
          }
          return fast;
      }
  };

  提示：Floyd判圈算法：对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd 判圈法）。给定两个指针，分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果 fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻 slow 和 fast 相遇。当 slow 和 fast 第一次相遇时，我们将 fast 重新移动到链表开头，并 让 slow 和 fast 每次都前进一步。当 slow 和 fast 第二次相遇时，相遇的节点即为环路的开始点。

五、练习

• 题目一：平方数之和
  给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c 。

  解答：

  class Solution {
  public:
      bool judgeSquareSum(int c) {
          if (c < 2) return true;
          int a = 0, b = sqrt(c);
          while (a <= b) {
              long sum = (long) a * a + (long) b * b;
              if (sum < c) ++a;
              else if (sum > c) --b;
              else return true;
          }
          return false;
      }
  };

  提示：最大值的选择为开方。

• 题目二：通过删除字母匹配到字典里最长单词
  给你一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。
  如果答案不止一个，返回长度最长且字母序最小的字符串。如果答案不存在，则返回空字符串。

  解答：

  class Solution {
  public:
      bool aHasb(string a, string b) {
          int i = 0, j = 0;
          while (i < a.length() && j < b.length()) {
              if (a[i] == b[j]) ++j;
              ++i;
          }
          return j == b.length();
      }
  
      string findLongestWord(string s, vector<string>& dictionary) {
          int res = -1;
          for (int i = 0; i < dictionary.size(); ++i) {
              if (res != -1 && (dictionary[i].length() < dictionary[res].length() || 					                (dictionary[i].length() == dictionary[res].length() && dictionary[i] >                                dictionary[res]))) continue;
              bool flag = aHasb(s, dictionary[i]);
              if (flag) res = i;
          }
          return res == -1 ? "" : dictionary[res];
      }
  };

  提示：双指针分别用于两个字符串的开头来判断包含关系。