1. 滑动窗口&set——无重复最长子串

示例:
输入: s = “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。**

  1. class Solution {
  2. public:
  3.     int lengthOfLongestSubstring(string s) {
  4.         // 哈希集合，记录每个字符是否出现过
  5.         unordered_set<char> occ;
  6.         int n = s.size();
  7.         // 右指针，初始值为 -1，相当于我们在字符串的左边界的左侧，还没有开始移动
  8.         int rk = -1, ans = 0;
  9.         // 枚举左指针的位置，初始值隐性地表示为 -1
  10.         for (int i = 0; i < n; ++i) {
  11.             if (i != 0) {
  12.                 // 左指针向右移动一格，移除一个字符
  13.                 occ.erase(s[i - 1]);
  14.             }
  15.             while (rk + 1 < n && !occ.count(s[rk + 1])) {
  16.                 // 不断地移动右指针
  17.                 occ.insert(s[rk + 1]);
  18.                 ++rk;
  19.             }
  20.             // 第 i 到 rk 个字符是一个极长的无重复字符子串
  21.             ans = max(ans, rk - i + 1);
  22.         }
  23.         return ans;
  24.     }
  25. };

扩展：
使用一种数据结构来判断 是否有重复的字符: 哈希集合（ C++ 中的 std::unordered_set ) 

  1. 法二： 哈希表维护字符对应的位置，并维护left变量
  2. class Solution {
  3. public:
  4.     int lengthOfLongestSubstring(string s) {
  5.         unordered_map<char,int> ch2pos;//位置范围1...n
  6.         int maxlen = 0, left = 1;
  7.         for(int i=0;i<s.size();i++){
  8.             if(ch2pos[s[i]] >= left){
  9.                 left = ch2pos[s[i]] + 1;
  10.             }
  11.             //其他情况；字符从出现过 或 在left位置之前
  12.             ch2pos[s[i]] = i+1;
  13.             maxlen = max(maxlen, i+1 - left + 1);
  14.         }
  15.         return maxlen;
  16.     }
  17. };

2. 单调栈——高楼数组

例题：小Q在周末的时候和他的小伙伴来到大城市逛街，一条步行街上有很多高楼，共有n座高楼排成一行。
小Q从第一栋一直走到了最后一栋，小Q从来都没有见到这么多的楼，所以他想知道他在每栋楼的位置处能看到多少栋楼呢？（当前面的楼的高度大于等于后面的楼时，后面的楼将被挡住）

输入描述:

输入第一行将包含一个数字n，代表楼的栋数，接下来的一行将包含n个数字w(1<=i<=n)，代表每一栋楼的高度。
1<=n<=100000;
1<=w<=100000;

输出描述:

输出一行，包含空格分割的n个数字v，分别代表小Q在第i栋楼时能看到的楼的数量。
示例1
输入
6
5 3 8 3 2 5
输出
3 3 5 4 4 4

说明**
当小Q处于位置3时，他可以向前看到位置2,1处的楼，向后看到位置4,6处的楼，加上第3栋楼，共可看到5栋楼。当小Q处于位置4时，他可以向前看到位置3处的楼，向后看到位置5,6处的楼，加上第4栋楼，共可看到4栋楼。

  1. #include <iostream>
  2. #include <vector>
  3. #include <stack>
  4. #include <algorithm>
  5. using namespace std;
  6. vector<int> a, b;
  7. stack<int> st1, st2;
  9. int main() {
  10.     int n, x[100001];
  11.     cin >> n;
  12.     int ans = 0;
  13.     for (int i = 0; i < n; i++) cin >> x[i];
  15.     for (int i = 0, j = n - 1; i < n, j >= 0; i++, j--) {
  16.         a.push_back(st1.size());
  17.         b.push_back(st2.size());
  19.         while (!st1.empty() && st1.top() <= x[i]) st1.pop();
  20.         while (!st2.empty() && st2.top() <= x[j]) st2.pop();
  21.         st1.push(x[i]);
  22.         st2.push(x[j]);
  23.     }
  24.     reverse(b.begin(), b.end());
  25.     for (int i = 0; i < n; i++) cout << b[i] + a[i] + 1<< " ";
  26.     return 0;
  27. }

3. 有序集合划分——求两个正序数组的中位数

4. 双指针

三数之和

  1. 题目：给你一个包含 n 个整数的数组 nums，
  2. 判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？
  3. 请你找出所有和为 0 且不重复的三元组。
  4. 注意：答案中不可以包含重复的三元组。
  6. 示例 1：
  7. 输入：nums = [-1,0,1,2,-1,-4]
  8. 输出：[[-1,-1,2],[-1,0,1]]

思路：利用有序数组中两数和为固定值时，可分别设双指针从首尾往中间查找。

  1. class Solution {
  2. public:
  3.     vector<vector<int>> threeSum(vector<int>& nums) {
  4.         //先排序
  5.         sort(nums.begin(),nums.end());
  6.         vector<vector<int> > res;
  7.         int n = nums.size();
  8.         for(int i=0;i<n;i++){
  9.             if(i>0&&nums[i]==nums[i-1]) continue;//跳过重复值
  11.             int j=i+1,k=n-1;
  12.             //固定nums[i]双指针移动j、k
  13.             while(j<k){
  14.                 if(j>i+1&&nums[j]==nums[j-1]){
  15.                     j++;continue;//跳过重复值
  16.                 }
  17.                 if(k<n-1&&nums[k]==nums[k+1]){
  18.                     k--;continue;//跳过重复值
  19.                 }
  21.                 if(nums[i] + nums[j] + nums[k] == 0){
  22.                     res.push_back({nums[i], nums[j], nums[k]});
  23.                     j++;k--;
  24.                 }else if(nums[i] + nums[j] + nums[k] > 0){
  25.                     k--;
  26.                 }else{
  27.                     j++;
  28.                 }
  29.             }
  31.         }
  32.         return res;
  33.     }
  34. };

三个间谍（滑动窗口）

  1. 题目：
  2. 我叫王大锤，是一名特工。我刚刚接到任务：
  3. 在字节跳动大街进行埋伏，抓捕恐怖分子孔连顺。
  4. 和我一起行动的还有另外两名特工，我提议
  5. 1. 我们在字节跳动大街的N个建筑中选定3个埋伏地点。
  6. 2. 为了相互照应，我们决定相距最远的两名特工间的距离不超过D。
  8. 请听题：给定N（可选作为埋伏点的建筑物数）、
  9. D（相距最远的两名特工间的距离的最大值）以及可选建筑的坐标，计算在这次行动中，大锤的小队有多少种埋伏选择。
  10. 注意：
  11. 1. 两个特工不能埋伏在同一地点
  12. 2. 三个特工是等价的：即同样的位置组合(A, B, C) 只算一种埋伏方法，不能因“特工之间互换位置”而重复使用
  14. 示例1
  15. 输入:
  16. 4 3
  17. 1 2 3 4
  18. 输出:
  19. 4
  20. 说明:
  21. 可选方案 (1, 2, 3), (1, 2, 4), (1, 3, 4), (2, 3, 4)
  1. #include <iostream> 
  2. #include <vector>
  3. using namespace std;
  5. long long C(long long n){
  6.     return (n-1) * n / 2;
  7. }
  9. int main()
  10. {
  11.     long long n, d, count = 0;
  12.     cin>> n>> d;
  13.     vector<long long> v(n);
  14.     for (int i = 0, j = 0; i < n; i++) {
  15.         cin>> v[i];
  16.         while (i >= 2 && (v[i] - v[j]) > d) {
  17.             j++;
  18.         }
  19.         count += C(i - j);
  20.     }
  21.     cout << count % 99997867; 
  22.     return 0;
  23. }

5. 前缀和/积

左右乘积列表——除自身以外数组的乘积

  1. 题目：给你一个长度为 n 的整数数组 nums，其中 n > 1，
  2. 返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
  4. 示例:
  5. 输入: [1,2,3,4]
  6. 输出: [24,12,8,6]
  8. 提示：题目数据保证数组之中任意元素的全部前缀元素和后缀（甚至是整个数组）的乘积都在 32 位整数范围内。
  9. 说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
  10. 进阶：你可以在常数空间复杂度内完成这个题目吗？

思路：res[i] = left[i] * right[i]

  1. class Solution {
  2. public:
  3.     vector<int> productExceptSelf(vector<int>& nums) {   
  4.         int n = nums.size();
  5.         vector<int> res(n,1);
  6.         int left = 1;
  7.         for(int i=0;i<n;i++){
  8.             if(i>0) left *= nums[i-1];
  9.             res[i] *= left;
  10.         }
  11.         int right=1;
  12.         for(int j=n-1;j>=0;j--){
  13.             if(j<n-1) right *= nums[j+1];
  14.             res[j] *= right;
  15.         }
  16.         return res;
  17.     }
  18. };

二维前缀和

题目：
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
数组与字符串 - 图1
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。

算法：利用二维前缀和
@{ECNQUO(E]}]ZU_RU%R`6A.png

  1. class NumMatrix {
  2.     vector<vector<int>> sums;
  3. public:
  4.     NumMatrix(vector<vector<int>>& matrix) {
  5.         int m=matrix.size(),n=matrix[0].size();
  6.         if(m>0){
  7.             sums.resize(m + 1, vector<int>(n + 1));
  8.             for(int i=0;i<m;i++){
  9.                 for(int j=0;j<n;j++){
  10.                     sums[i+1][j+1] = sums[i+1][j] + sums[i][j+1] - sums[i][j] + matrix[i][j];
  11.                 }
  12.             }
  13.         }
  15.     }
  17.     int sumRegion(int row1, int col1, int row2, int col2) {
  18.         return sums[row2+1][col2+1] + sums[row1][col1] - sums[row1][col2+1] - sums[row2+1][col1];
  19.     }
  20. };
  22. /**
  23.  * Your NumMatrix object will be instantiated and called as such:
  24.  * NumMatrix* obj = new NumMatrix(matrix);
  25.  * int param_1 = obj->sumRegion(row1,col1,row2,col2);
  26.  */

6. 大数加法——字符串相加

思路：从后往前串行相加，数据不够按0相加。

  1. class Solution {
  2. public:
  3.     string addStrings(string num1, string num2) {
  4.         int i = num1.length() - 1, j = num2.length() - 1, add = 0;
  5.         string ans = "";
  6.         while (i >= 0 || j >= 0 || add != 0) {
  7.             int x = i >= 0 ? num1[i] - '0' : 0; //技巧：首部无值时补零
  8.             int y = j >= 0 ? num2[j] - '0' : 0;
  9.             int result = x + y + add;
  10.             ans.push_back('0' + result % 10);
  11.             add = result / 10;
  12.             i -= 1;
  13.             j -= 1;
  14.         }
  15.         // 计算完以后的答案需要翻转过来
  16.         reverse(ans.begin(), ans.end()); //翻转数组
  17.         return ans;
  18.     }
  19. };

7. KMP+最大不相交集合—— 寻找子串

题目：
给出m个字符串S1，S2，…，Sm和一个单独的字符串T。请在T中选出尽可能多的子串同时满足：
1）这些子串在T中互不相交。
2）这些子串都是S1，S2，…，Sm中的某个串。
问最多能选出多少个子串。

思想：
使用KMP算法得到能在T中找到的子串的首尾索引
再对得到的集合序列排序，按尾部从小到大排，按贪心算法求解。

  1. #include <bits/stdc++.h>
  2. using namespace std;
  4. const int N = 100003;
  5. int dp[N], nxt[N];
  6. vector<vector<int>>    v;
  8. void Next(string t){
  9.     int i=0, j=-1, n=t.length();
  10.     nxt[0] = -1;
  11.     while(i<n){
  12.         if(j==-1 || t[i]==t[j])
  13.             nxt[++i] = ++j;
  14.         else
  15.             j = nxt[j];
  16.     }
  17. }
  19. void KMP(string s, string t){
  20.     Next(t);
  21.     int n=s.length(), m=t.length(), i=0, j=0;
  22.     while(i<n){
  23.         if(j==-1 || s[i]==t[j]){
  24.             i++;
  25.             j++;
  26.         }else
  27.             j = nxt[j];
  28.         if(j==m){
  29.             v.push_back({i - 1, i - m});
  30.             j = nxt[j];
  31.         }
  32.     }
  33. }
  35. int main(){
  36.     int n;
  37.     cin>>n;
  38.     string s, t[n];
  39.     for(int i=0;i<n;i++)
  40.         cin>>t[i];
  41.     cin>>s;
  42.     for(int i=0;i<n;i++)
  43.         KMP(s, t[i]);
  45.     sort(v.begin(),v.end());
  46.     int l = v.size();
  47.     int count = 0, start = 0;
  48.     for(int i = 0; i < l; ++i){
  49.         if(v[i][1] < start)    continue;
  50.         ++count;
  51.         start = v[i][0] + 1;
  52.     }
  53.     cout<<count;
  54.     return 0;
  55. }

8. 二分查找

小Q的父母要出差N天，走之前给小Q留下了M块巧克力。小Q决定每天吃的巧克力数量不少于前一天吃的一半，但是他又不想在父母回来之前的某一天没有巧克力吃，请问他第一天最多能吃多少块巧克力

输入描述:
每个输入包含一个测试用例。
每个测试用例的第一行包含两个正整数，表示父母出差的天数N(N<=50000)和巧克力的数量M(N<=M<=100000)。
输出描述:
输出一个数表示小Q第一天最多能吃多少块巧克力。

示例1
输入
3 7
输出
4

  1. #include<iostream>
  2. using namespace std;
  3. int n,m;
  4. //计算第一天吃s个巧克力一共需要多少个多少个巧克力
  5. int sum(int s){
  6.     int sum=0;
  7.     for(int i=0;i<n;i++){
  8.         sum+=s;
  9.         s=(s+1)>>1;//向上取整
  10.     }
  11.     return sum;
  12. }
  13. //二分查找
  14. int fun(){
  15.     if(n==1) return m;
  16.     int low=1;
  17.     int high=m;//第一天的巧克力一定是大于等于1小于等于m的
  18.     while(low<high){
  19.         int mid=(low+high+1)>>1;//向上取整
  20.         if(sum(mid)==m) return mid;//如果第一天吃mid个巧克力，刚刚好吃完所有巧克力，那么直接返回
  21.         else if(sum(mid)<m){
  22.             low = mid;  //此边界条件我很迷糊
  23.         }else{
  24.             high=mid - 1;
  25.         }
  26.     }
  27.     return high;
  28. }
  29. int main()
  30. {
  31.     cin>>n>>m;
  32.     int res=fun();
  33.     cout<<res<<endl;
  34.     return 0;
  35. }

9. 滑动窗口——爱生气的书店老板

题目：
今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
在某些时候，书店老板会生气。 如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的。
书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次。
请你返回这一天营业下来，最多有多少客户能够感到满意的数量。
示例：
输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出：16
解释：
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

算法思想：
使用「秘密技巧」能得到的最终的顾客数 = 所有不生气时间内的顾客总数 + 在窗口 X 内使用「秘密技巧」挽留住的原本因为生气而被赶走顾客数。

因此，可以把题目分为以下两部分求解：
（1）所有不生气时间内的顾客总数：使用 ii 遍历[0, customers.length)[0,customers.length)，累加grumpy[i] == 0grumpy[i]==0时的customers[i]customers[i]。
（2）在窗口 X 内因为生气而被赶走的顾客数：使用大小为 X 的滑动窗口，计算滑动窗口内的grumpy[i] == 1grumpy[i]==1时的customers[i]customers[i]，得到在滑动窗口内老板生气时对应的顾客数。

  1. class Solution:
  2.     def maxSatisfied(self, customers: List[int], grumpy: List[int], X: int) -> int:
  3.         N = len(customers)
  4.         sum_ = 0
  5.         # 所有不生气时间内的顾客总数
  6.         for i in range(N):
  7.             if grumpy[i] == 0:
  8.                 sum_ += customers[i]
  9.         # 生气的 X 分钟内，会让多少顾客不满意
  10.         curValue = 0
  11.         # 先计算起始的 [0, X) 区间
  12.         for i in range(X):
  13.             if grumpy[i] == 1:
  14.                 curValue += customers[i]
  15.         resValue = curValue
  16.         # 然后利用滑动窗口，每次向右移动一步
  17.         for i in range(X, N):
  18.             # 如果新进入窗口的元素是生气的，累加不满意的顾客到滑动窗口中
  19.             if grumpy[i] == 1:
  20.                 curValue += customers[i]
  21.             # 如果离开窗口的元素是生气的，则从滑动窗口中减去该不满意的顾客数
  22.             if grumpy[i - X] == 1:
  23.                 curValue -= customers[i - X]
  24.             # 求所有窗口内不满意顾客的最大值
  25.             resValue = max(resValue, curValue)
  26.         # 最终结果是：不生气时的顾客总数 + 窗口X内挽留的因为生气被赶走的顾客数
  27.         return sum_ + resValue

10. 买卖股票的最佳时机

一次买卖——一次遍历

题目：给定一个股票价格序列，从某一天买入，并从另一天卖出，返回最大利润。

法一：（维护当前卖出股票时，历史最低价的股票）
如果我是在历史最低点买的股票就好了！太好了，在题目中，我们只要用一个变量记录一个历史最低价格 minprice，我们就可以假设自己的股票是在那天买的。
那么我们在第 i 天卖出股票能得到的利润就是 prices[i] - minprice。
法二：（维护当前买入股票时，未来最高价的股票）倒序维护一个maxprice记录一个未来最高价格 

  1. 法一：
  2. class Solution {
  3. public:
  4.     int maxProfit(vector<int>& prices) {
  5.         int inf = 1e9;
  6.         int minprice = inf, maxprofit = 0;
  7.         for (int price: prices) {
  8.             maxprofit = max(maxprofit, price - minprice);
  9.             minprice = min(price, minprice);
  10.         }
  11.         return maxprofit;
  12.     }
  13. };
  15. 法二：
  16. class Solution {
  17. public:
  18.     int maxProfit(vector<int>& prices) {
  19.         int n = prices.size();
  20.         int maxstock=-1, maxprofit  = 0;
  21.         for (int i = n - 1; i >= 0;i--){
  22.             maxstock = max(maxstock, prices[i]);
  23.             if(maxstock > prices[i]){
  24.                 maxprofit = max(maxprofit, maxstock - prices[i]);
  25.             }
  26.         }
  27.         return maxprofit;
  28.     }
  29. };

多次买卖

题目：**可以多次买卖，买一个新股票时手里不能留有股票。求最大利润。
方法：**求所有升序和。

  1. class Solution {
  2. public:
  3.     int maxProfit(vector<int>& prices) {
  4.         int n = prices.size();
  5.         int sum = 0;
  6.         for(int i=1; i<n;i++){
  7.             if(prices[i] - prices[i-1] > 0){
  8.                 sum += prices[i] - prices[i-1];
  9.             }
  10.         }
  11.         return sum;
  12.     }
  13. };