title: LC101の2. 双指针
urlname: bnq65f
date: ‘2021-05-13 14:06:0’
tags: [双指针]
categories: [算法刷题]

算法解释

顾名思义，通过两个指针遍历数组，协同完成任务。
遍历方向相同且不会相交的，可称为滑动窗口。
遍历方向相反，则可以用来搜索。

Two Sum

[167] Two Sum II - Input array is sorted
题目描述：找到和为定值的两个数
输入输出：Input: numbers = [2,7,11,15], target = 9 Output: [1,2]
题解：在头尾处用两个指针往中间遍历，如果和小了，左指针右移，反之右指针左移。
代码：

  1.     vector<int> twoSum(vector<int>& numbers, int target) {
  2.         int begin = 0,end = numbers.size() - 1;
  3.         while(begin < end){
  4.             int sum = numbers[begin] + numbers[end];
  5.             if(sum == target)break;
  6.             else if(sum > target)end--;
  7.             else begin++;
  8.         }
  9.         return vector<int>{begin + 1, end + 1};
  10.     }

归并两个有序数组

[88] Merge Sorted Array
题目描述：将第二个数组合并到第一个上。
输入输出：Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6]
题解：从尾巴开始添加，对比 num1 和 num2 的末尾哪个更小，从后往前遍历。
代码：

  1.     void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
  2.         int k = m + n - 1;
  3.         while(m > 0 && n > 0){
  4.             nums1[k--] = nums1[m - 1] > nums2[n - 1]? nums1[--m]: nums2[--n];
  5.         }
  6.         while(n > 0){
  7.             nums1[k--] = nums2[--n];
  8.         }
  9.     }

快慢指针

[142] Linked List Cycle II
题目描述：给定一个链表，有环路返回开始点，否则返回空指针。
输入输出：Input: head = [3,2,0,-4], pos = 1 Output: tail connects to node index 1
题解：链表找环路通用解法-快慢指针（Floyd 判圈法）：
代码：Floyd 判圈法可列数学式子推导而出。【参考链接】

  1.     ListNode *detectCycle(ListNode *head) {
  2.         ListNode *slow = head, *fast = head;
  3.         do{
  4.             if(!fast || !fast->next)return NULL;
  5.             fast = fast->next->next;
  6.             slow = slow->next;
  7.         }while(fast != slow);
  8.         fast = head;
  9.         while(fast != slow){
  10.             fast = fast->next;
  11.             slow = slow->next;
  12.         }
  13.         return fast;
  14.     }

滑动窗口

[76] Minimum Window Substring
题目描述：字符串 S 和 T，求 S 中包含 T 所有字符最短连续子串长度，时间复杂度不超过 O(n)
输入输出：Input: s = “ADOBECODEBANC”, t = “ABC” Output: “BANC”
题解：
代码：（参考答案）

  1.     string minWindow(string s, string t) {
  2.         int cnt = t.size(), k = 0;
  3.         vector<int> num(128,0);
  4.         vector<bool> flag(128,false);
  5.         for(int i = 0; i < cnt; i++){
  6.             flag[t[i]] = true;
  7.             num[t[i]]++;
  8.         }
  9.         int l = 0, m_l = 0, m_len = s.size() + 1;
  10.         for(int r = 0; r < s.size(); r++){
  11.             if(flag[s[r]]){
  12.                 if(num[s[r]]-- > 0)
  13.                     k++;
  14.                 while(k == cnt){
  15.                     if(r - l + 1 < m_len){
  16.                         m_len = r - l + 1;
  17.                         m_l = l;
  18.                     }
  19.                     if(flag[s[l]] && ++num[s[l]] > 0){
  20.                         k--;
  21.                     }
  22.                     l++;
  23.                 }
  24.             }
  25.         }
  26.         return m_len > s.size()? "": s.substr(m_l, m_len);
  27.     }

练习

[633] Sum of Square Numbers
题目描述：输入一个数 c，是否存在 a，b 平方和为 c
输入输出：Input: c = 5 Output: true
题解：使用头尾双指针，数据过大需要使用 long
代码：

  1.     bool judgeSquareSum(int c) {
  2.         long l = 0, r = (int)sqrt(c);
  3.         int flag = false;
  4.          while(l <= r){
  5.             long sum = l * l + r * r;
  6.             if(sum > c){
  7.                 r--;
  8.             }else if(sum < c){
  9.                 l++;
  10.             }else{
  11.                 flag = true;
  12.                 break;
  13.             }
  14.         }
  15.         return flag;
  16.     }

[680] Valid Palindrome II
题目描述：是否可以删除最多一个字符使输入串为回文串
输入输出：Input: s = “abca” Output: true
题解：双指针，遍历冲突时处理删左和删右两种情况
代码：（参考答案）

  1.     bool validPalindrome(string s) {
  2.         int l = 0, r = s.size() - 1;
  3.         while(l <= r){
  4.             if(s[l] != s[r]){
  5.                 int i1 = l, j1 = r - 1,i2 = l + 1, j2 = r;
  6.                 while (i1 < j1 && s[i1] == s[j1]) {i1++; j1--;};
  7.                 while (i2 < j2 && s[i2] == s[j2]) {i2++; j2--;};
  8.                 return i1 >= j1 || i2 >= j2;
  9.             }
  10.             l++;
  11.             r--;
  12.         }
  13.         return true;
  14.     }

[524] Longest Word in Dictionary through Deleting
题目描述：字符串 s 和字符串数组 d，找出，可以由 s 删除部分字符得到的 d 中最长字符串，若一样长取字符串小的。
输入输出：Input: s = “abpcplea”, dictionary = [“ale”,”apple”,”monkey”,”plea”] Output: “apple”
题解：暴力。
代码：

  1.     string findLongestWord(string s, vector<string>& d) {
  2.         int max_l = 0;
  3.         string max_s = "";
  5.         for(int i = 0; i < d.size(); i++){
  6.             //比较s,d[i]
  7.             int j = 0, k = 0;
  8.             for(; k < s.size(); k++){
  9.                 if(d[i][j] == s[k])
  10.                     j++;
  11.             }
  12.             if(j == d[i].size()){
  13.                 if(d[i].size() > max_l){
  14.                     max_l = d[i].size();
  15.                     max_s = d[i];
  16.                 }else if(d[i].size() == max_l && max_s > d[i]){
  17.                     max_s = d[i];
  18.                 }
  19.             }
  20.         }
  21.         return max_s;
  22.     }