一般数组，或字符串类型的数据进行处理，就要思考双指针能够解决，包括快慢指针，首尾指针，滑动窗口等。

快慢指针

457环形数组是否存在循环

本题查看数组里面是否有达成要求的循环。非常类似141环形链表，剪枝思想也十分经典，已经遇到几次这种去重的操作，总是写不出来，记录一下。

  1. class Solution {
  2. public:
  3.     bool circularArrayLoop(vector<int>& nums) {
  4.         int n = nums.size();
  5.         auto next = [&](int cur) {//注意使用lambda表达式
  6.             return ((cur + nums[cur]) % n + n) % n; // 保证返回值在[0,n) 中
  7.         };
  9.         for (int i = 0; i < n; i++) {//这里的i指的是起点，在每一个起点判断下面的情况。
  10.             int slow = i, fast = next(i);//慢指针是i，快指针是next，满指针一次走一位，快指针一次走两个
  11.             //写题的思路有点类似找到链表里面的循环
  12.             //判断非零且方向相同
  13.             while (nums[slow] * nums[fast] > 0 && nums[slow] * nums[next(fast)] > 0) {
  14.                 if (slow == fast) {
  15.                     if (slow != next(slow)) {//这排除了k=1的情况。
  16.                         return true;
  17.                     } else {
  18.                         break;
  19.                     }
  20.                 }
  21.                 slow = next(slow);
  22.                 fast = next(next(fast));
  23.             }
  24.             int add = i;
  25.             while (nums[add] * nums[next(add)] > 0) {
  26.                 int tmp = add;
  27.                 add = next(add);
  28.                 nums[tmp] = 0;//这里是一步剪枝操作，因为如果符号相同，从i起步的顺序都已经走过了。直接置为零
  29.                 //防止后期重复走
  30.             }
  31.         }
  32.         return false;
  33.     }
  34. };

141环形链表

使用快慢指针的方法，慢指针走一步，快指针走两步，当相遇的时候就代表有循环。

142. 环形链表 II

相比环形链表，还需要知道循环的起始点在哪里。
这里使用floyd判圈法

  • 给定两个指针，分别命名为fast和slow，每次fast前进两步，slow前进一步。
  • 如果fast可以走到尽头，那么说明没有i环路；如果fast可以无线走下去那就说明一定有循环，并且fast一定会和slow相遇
  • 当slow和fast第一次相遇之后，我们将fast重新移动到链表的开头，并让fast同样每次只前进一步。第二次相遇时就一定是环路的起步节点。
  • 这里的do while 的形式很重要，防止了初始fast与slow相等的情况。
    1. class Solution {
    2. public:
    3.   ListNode *detectCycle(ListNode *head) {
    4.       ListNode*slow = head, *fast = head;
    5.       do{
    6.           if(!fast||!fast->next) return NULL;
    7.           fast = fast->next->next;
    8.           slow = slow->next;
    9.       } while (fast != slow);
    10.       fast = head;
    11.       while(fast != slow){
    12.           slow = slow->next;
    13.           fast = fast->next;
    14.       }
    15.       return fast;
    16.   }
    17. };

剑指offer22链表中倒数第k个节点

这一题，用顺序遍历非常简单，但是用快慢指针属实是没想到。有点类似滑动窗口的思想，保证快节点与慢节点之间差k，等到快节点到尾部，慢节点就是倒数第k个节点的位置。

  1. class Solution {
  2. public:
  3.     ListNode* getKthFromEnd(ListNode* head, int k) {
  4.         ListNode* fast = head;
  5.         ListNode* slow = head;
  7.         while (fast && k > 0) {
  8.             fast = fast->next;
  9.             k--;
  10.         }
  11.         while (fast) {
  12.             fast = fast->next;
  13.             slow = slow->next;
  14.         }
  16.         return slow;
  17.     }
  18. };

1089. 复写零(这题也可以说类似快慢指针)

  • 为了实现复写零的特点，可以用栈来模拟，当栈里面的元素有n个的时候就重写回数组。
  • 但是不用独立开辟一个栈空间，可以直接在原数组上面模拟栈即可。当top>=n的时候，从i往前的元素实际上就是栈里面的元素，不过栈里面的元素复写了。
    1. class Solution {
    2.   public:
    3.   void duplicateZeros(vector<int>& arr) {
    4.       int n = arr.size();
    5.       int top = 0, i = 0;
    6.       for(;i < n; i++) {
    7.           if(arr[i] == 0) {
    8.               top += 2;
    9.           } else top ++;
    10.           if(top >= n) break;
    11.       }
    12.       int j = n-1;//这里的j表示从后往前对数组进行修改，j从最后一位开始。
    13.       if(top > n) {//这里的top > n，代表i的位置可能为0，使得top超过了n。这种情况，特殊处理。
    14.           arr[j] = 0;
    15.           i--;
    16.           j--;
    17.       }
    18.       for(; j >= 0; j--) {
    19.           arr[j] = arr[i];
    20.           if(arr[i] == 0) {
    21.               j--;
    22.               arr[j] = arr[i];
    23.           }
    24.           i--; 
    25.       }
    26.   }
    27. };

    首尾双指针

167. 两数之和 II - 输入有序数组(经典简单)

  1. class Solution {
  2. public:
  3.     vector<int> twoSum(vector<int>& numbers, int target) {
  4.         int l = 0, r = numbers.size()-1, sum;
  5.         while(l < r){
  6.             sum = numbers[l] + numbers[r];
  7.             if(sum == target) break;
  8.             if(sum < target) l++;
  9.             else r--;
  10.         }
  11.         return vector<int>{l+1, r+1};
  12.     }
  13. };

633. 平方数之和(两数之和变形题)

有几个点

  • sum的超出int范围的问题
  • 在c++里面，1/2 = 0，因为是两个整数，然后向下取整，想要得到0.5直接输入0.5或者1.0/2.0

  • 在这种情况下 l 能够 与r相等

    1. class Solution {
    2. public:
    3.   bool judgeSquareSum(int c) {
    4.       int l = 0, r = ceil(pow(c, 1.0/2.0));
    5.       while(l <= r){
    6.           long sum = pow(l, 2) + pow(r, 2);
    7.           if(sum > c){
    8.               r --;
    9.           } else if(sum < c){
    10.               l ++;
    11.           } else {
    12.               return true;
    13.           }
    14.       }
    15.       return false;
    16.   }
    17. };

    680. 验证回文字符串 Ⅱ（可以看）

    无法一次实现的时候，可以另外写一个函数！！！！

    1. class Solution {
    2. public:
    3.   bool checkPalindrome(const string& s, int low, int high) {
    4.       for (int i = low, j = high; i < j; ++i, --j) {
    5.           if (s[i] != s[j]) {
    6.               return false;
    7.           }
    8.       }
    9.       return true;
    10.   }
    12.   bool validPalindrome(string s) {
    13.       int low = 0, high = s.size() - 1;
    14.       while (low < high) {
    15.           char c1 = s[low], c2 = s[high];
    16.           if (c1 == c2) {
    17.               ++low;
    18.               --high;
    19.           } else {
    20.               return checkPalindrome(s, low, high - 1) || checkPalindrome(s, low + 1, high);
    21.           }
    22.       }
    23.       return true;
    24.   }
    25. };

    345反转字符串种的元音字母

    这一题使用两个指针，分别从字符串的首位和末尾开始遍历。如果i < j并且都是元音字母则swap，注意此代码块中的string::npos代表不存在的位置，即字符串查找不到的结果。

    1. class Solution {
    2. public:
    3.   string reverseVowels(string s) {
    4.       string vowels = "aeiouAEIOU";
    5.       auto isVowel = [&](char ch) {//npos是一个常数，用来表示不存在的位置
    6.           return vowels.find(ch) != string::npos;
    7.       };
    9.       int n = s.size();
    10.       int i = 0, j = n - 1;
    11.       while (i < j) {
    12.           while (i < n && !isVowel(s[i])) {
    13.               ++i;
    14.           }
    15.           while (j > 0 && !isVowel(s[j])) {
    16.               --j;
    17.           }
    18.           if (i < j) {
    19.               swap(s[i], s[j]);
    20.               ++i;
    21.               --j;
    22.           }
    23.       }
    24.       return s;
    25.   }
    26. };

    75. 颜色分类(经典荷兰国旗题目)

    要有这种想法，这题只有三种元素用快排复杂度会高一点O(NLOGN)。使用双指针为O(N)

    首尾双指针

    class Solution {
public:
  void sortColors(vector<int>& nums) {
      int n = nums.size();
      if(n < 2) return;
      int p = 0, q = n-1;
      for(int i = 0; i <= q; i++){
          if(nums[i]==0){
              swap(nums[i], nums[p++]);
          } else if(nums[i] == 2){
              swap(nums[i], nums[q--]);
              if(nums[i]!=1){
                  i--;
              }
          }
      }
      return;
  }
};

    头部双指针

    平行的两种情况，一定得加else

    class Solution {
public:
  void sortColors(vector<int>& nums) {
      int n = nums.size(), p = 0, q = 0;
      if(n < 2) return; 
      for(int i = 0; i < n; i++){
          if(nums[i] == 0){
              swap(nums[i], nums[p++]);
              if(nums[i] == 1){
                  swap(nums[q], nums[i]);
              }
              q++;
          }else if(nums[i] == 1){
              swap(nums[q++], nums[i]);
          }
      }
      return;
  }
};

    870. 优势洗牌（田忌赛马）

  • 将nums1和nums2都从大到小排序

  • 关键在于nums排序的时候应该保存下标，因为最终的nums1数组应该对应nums2的下标
  • 用nums1的最尾部与nums2的最尾部进行对比，如果大于则填入，如果小于则将最nums1的最前部填入

  • 也就是说如果满足条件则填入，如果不满足条件则填入最小值，减少损失

    class Solution 
{
public:
  vector<int> advantageCount(vector<int>& A, vector<int>& B)//方法2
  {
      vector<pair<int,int>>v;
      vector<int>ans(A.size(),-1);

      for(int i=0;i<B.size();i++)
          v.push_back(make_pair(B[i],i));//pair排序默认按第一关键字升序,若第一关键字相同再按第二关键字

      sort(A.begin(),A.end());
      sort(v.begin(),v.end());

      int Al = 0,Ar = A.size()-1,Br = v.size()-1;
      while(Br >= 0)
      {
          if(A[Ar] > v[Br].first)//Amax>Bmax  Amax去对位Bmax
          {
              ans[v[Br].second] = A[Ar];
              Ar--;
          }
          else//Amax<Bmax   Amin去对位Bmax
          {
              ans[v[Br].second] = A[Al];
              Al++;
          }
          Br--;
      }
      return ans;
  }
};

双指针指向不同数组

88. 合并两个有序数组（归并排序的一部分）

我的笨比写法

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        vector<int> tmp(m+n);
        int i = 0, j = 0,k = 0;
        while(i < n && j < m){
            if(nums1[j] >= nums2[i]){
                tmp[k++] = nums2[i++];
            } else {
                tmp[k++] = nums1[j++];
            }
        }
        if(i == n){
            for(j; j < m; j++){
                tmp[k++] = nums1[j];
            }
        } else if(j == m){
            for(i; i < n; i++){
                tmp[k++] = nums2[i];
            }
        }
        for(int a = 0; a < n+m; a++){
            nums1[a] = tmp[a];
        }
    }
};

高手写法（巧妙）

但是可读性不是很好
因为这里的nums1数组是预留的m+n个空间，但是只有前m个有数据。所以可以直接把合并之后的数组存在nums1数组，但是为了避免覆盖原来的数据，应该从后面从大到小开始合并。这里有一个重点，当m<0或者n < 0 时有两种情况

  • m < 0时，nums1前半个数据已经完全合并完，此时将nums2剩下的数据直接赋值给nums1即可

  • n < 0时， nums2的所有数据已经完全合并完，因为时非递减序列，且nums1的数据原本就在里面，所以直接完成了。

    class Solution {
public:
  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--];
      }
  }
};

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

    归并两个有序数组的变形题

    class Solution {
public:
  string findLongestWord(string s, vector<string>& dictionary) {
      int n = s.size(), num = 0;
      string ret;
      for(auto it : dictionary){
          int m = it.size();
          for(int i = 0, j = 0; i < n&&j < m; i++){
              if(s[i] == it[j]) j++;
              if(j == m){
                  if(m > num) {
                      ret = it;
                      num = m;
                  } else if(m == num){
                      ret = ret<it? ret:it; 
                  }
              }
          }
      }
      return num == 0? "":ret;
  }
};

    滑动窗口

    76. 最小覆盖子串

    这一题写的时候出现一几个问题，在这里列举一下，引以为戒

  • 有一个地方的while写成了if，检查了老半天

  • 第一次提交没有考虑到，缩小左边界时，已存在的字符问题
  • 熟练使用哈希表的count函数的特点

  • class Solution {
public:
  string minWindow(string s, string t) {
      unordered_map<char, int> hash;
      int num = 0 ,ret = INT_MAX,start = 0 ;
      for(auto it : t){
          hash[it]++;
          num++;
      }
      int n = s.size();
      for(int i = 0, j = 0; i < n&&j < n;j++){
          if(hash.count(s[j]) == 1){
              if(hash[s[j]] > 0){
                  num--;
              }
              hash[s[j]]--;
          }
          if(num == 0){
              while(hash.count(s[i]) == 0||(hash.count(s[i]) == 1&&hash[s[i]] < 0)){
                  if(hash.count(s[i]) == 1){
                      hash[s[i]]++;
                  }
                  i++;
              }
              if(ret > j - i + 1){
                  ret = j - i + 1;
                  start = i;
              }
              hash[s[i++]]++;
              num++;
          }
      }
      return ret == INT_MAX? "":s.substr(start, ret);
  }
};

    594. 最长和谐子序列(简单滑窗)

    我们可以枚举数组中的每一个元素，对于当前枚举的元素 xx，它可以和 x+1 组成和谐子序列。我们只需要在数组中找出等于 x 或 x+1 的元素个数，就可以得到以 x 为最小值的和谐子序列的长度。

实际处理时，我们可以将数组按照从小到大进行排序，我们只需要依次找到相邻两个连续相同元素的子序列，检查该这两个子序列的元素的之差是否为 1。
利用类似与滑动窗口的做法，begin 指向第一个连续相同元素的子序列的第一个元素，end 指向相邻的第二个连续相同元素的子序列的末尾元素，如果满足二者的元素之差为 11，则当前的和谐子序列的长度即为两个子序列的长度之和，等于end−begin+1。

class Solution {
public:
    int findLHS(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        int begin = 0;
        int res = 0;
        for (int end = 0; end < nums.size(); end++) {
            while (nums[end] - nums[begin] > 1) {
                begin++;
            }
            if (nums[end] - nums[begin] == 1) {
                res = max(res, end - begin + 1);
            }
        }
        return res;
    }
};

2134. 最少交换次数来组合所有的 1 II（拼接数组+滑动窗口）

  • 将数组拼接在一起就可以看作是首尾相连了。
  • 通过滑动窗口维护长度为k的范围，k是原数组中1的数据
  • 使用k-当前范围1的数据就可以得到当前范围0的数据
  • 当前范围0的数据就是需要交换的次数
    class Solution {
public:
int minSwaps(vector<int>& nums) {
  int k = 0;//k来计算nums有多少个1
  for (auto num: nums) {
    if (num == 1) k++;
  }
  if (k <= 1) return 0;
  vector<int> ring = nums;
  ring.insert(ring.end(), nums.begin(), nums.end());//ring是把两个数组连载一起！！！！
  //这种方法在解决循环数组里面非常常见。也可以使用循环两次来实现
  int n = ring.size();
  int cnt = 0;
  int ans = INT_MAX;
  for (int i = 0, j = 0; i < n&&j < n; ++i) {
    if (ring[i] == 1) cnt++;
    if(i-j == k-1){
        ans = min(ans, k - cnt);
        if(ring[j] == 1){
            cnt--;
        }
        j++;
    }
  }
  return ans;
}
};

    30. 串联所有单词的子串（困难滑窗）

    记 words 的长度为 m，words 中每个单词的长度为 n，s 的长度为 ls。首先需要将 s 划分为单词组，每个单词的大小均为 n （首尾除外）。这样的划分方法有 n 种，即先删去前 i （i = 0∼n−1）个字母后，将剩下的字母进行划分，如果末尾有不到 n 个字母也删去。对这 n 种划分得到的单词数组分别使用滑动窗口对 words 进行类似于「字母异位词」的搜寻。
    划分成单词组后，一个窗口包含 s 中前 m 个单词，用一个哈希表 differ 表示窗口中单词频次和 words 中单词频次之差。初始化 differ 时，出现在窗口中的单词，每出现一次，相应的值增加 1，出现在 words 中的单词，每出现一次，相应的值减少 1。然后将窗口右移，右侧会加入一个单词，左侧会移出一个单词，并对differ 做相应的更新。窗口移动时，若出现 differ 中值不为 0 的键的数量为 0，则表示这个窗口中的单词频次和 words 中单词频次相同，窗口的左端点是一个待求的起始位置。划分的方法有 n 种，做 n 次滑动窗口后，即可找到所有的起始位置。
    class Solution {
public:
  vector<int> findSubstring(string &s, vector<string> &words) {
      vector<int> res;
      int m = words.size(), n = words[0].size(), ls = s.size();
      for (int i = 0; i < n && i + m * n <= ls; ++i) {//N种不同的划分方式
          unordered_map<string, int> differ;
          for (int j = 0; j < m; ++j) {
              ++differ[s.substr(i + j * n, n)];
          }//对s进行划分，这个是第一个窗口
          for (string &word: words) {
              if (--differ[word] == 0) {
                  differ.erase(word);
              }//把这个窗口里面所有频次为0的情况删除，因为已经满足。如果这个窗口为空则满足条件。
          }
          for (int start = i; start < ls - m * n + 1; start += n) {
              if (start != i) {//滑到下一个窗口，start就是当前窗口的第一个元素。
                  string word = s.substr(start + (m - 1) * n, n);//新元素加进去
                  if (++differ[word] == 0) {
                      differ.erase(word);
                  }
                  word = s.substr(start - n, n);//旧元素删除掉
                  if (--differ[word] == 0) {
                      differ.erase(word);
                  }
              }
              if (differ.empty()) {//为空表示找到一种情况。
                  res.emplace_back(start);
              }
          }
      }
      return res;
  }
};