可能用到的STL算法一览

前缀和计算: partial_sum

使用方法:

std::partial_sum - cppreference.com;

#include <numeric>
#include <vector>
#include <iostream>
#include <iterator>
#include <functional>
void t1() {
    std::vector<int> v = {2, 2, 2, 2, 2,
                          2, 2, 2, 2, 2}; // 或 std::vector<int>v(10, 2);

    std::cout << "前 10 个偶数是：";
    std::partial_sum(v.begin(), v.end(),
                     std::ostream_iterator<int>(std::cout, " "));
    std::cout << '\n';

    std::partial_sum(v.begin(), v.end(), v.begin(), std::multiplies<int>());

    std::cout << "2 的前 10 个幂是：";
    for (auto n : v) std::cout << n << " ";
    std::cout << '\n';
}


void t2() {
    using namespace std;
    vector<int> v{1, 2, 3, 4, 5};
    vector<int> ans(v.size() + 1);
    struct f {
        constexpr int operator()(const int& lhs, const int& rhs) {
            return lhs + rhs;
        }
    };
    // partial_sum(v.begin(), v.end(), ans.begin() + 1, plus<int>());
    // partial_sum(v.begin(), v.end(), ans.begin() + 1, f());
    partial_sum(v.begin(), v.end(), ans.begin() + 1,
                [](const int& lhs, const int& rhs) { return lhs + rhs; });
    for (auto i : ans) cout << i << " ";
    cout << endl;
}

int main() {
    // t1();
    t2();
    return 0;
}

二分下界: lower_bound

基本题目

1. 面试题 16.24. 数对和 - 力扣（LeetCode）;(二分的思想)

   class Solution {
   public:
       vector<vector<int>> pairSums(vector<int>& nums, int target) {
           sort(nums.begin(), nums.end());
           vector<vector<int>> ans{};
           int l{}, r = nums.size() - 1;
           while (l < r) {
               int tmp{nums[l] + nums[r]};
               if (tmp == target)
                   ans.emplace_back(vector<int>{nums[l++], nums[r--]});
               else if (tmp > target)
                   --r;
               else
                   ++l;
           }
           return ans;
       }
   };
   

2. 剑指 Offer 04. 二维数组中的查找;240. 搜索二维矩阵 II;

   class Solution {
   public:
       bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
           if (matrix.empty()) return false;
           int n = matrix.size(), m = matrix[0].size();
           int r{0}, c{m - 1}; // 右上角
           while (c >= 0 && r < n) {
               if (matrix[r][c] == target)
                   return true;
               else if (matrix[r][c] > target)
                   --c;
               else
                   ++r;
           }
           return false;
       }
   };
   // 左下角: r, c 换一下
   class Solution {
   public:
       bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
           if (matrix.empty()) return false;
           int n = matrix.size(), m = matrix[0].size();
           int r{n - 1}, c{}; // 左下角
           while (r >= 0 && c < m) {
               if (matrix[r][c] == target)
                   return true;
               else if (matrix[r][c] > target)
                   --r;
               else
                   ++c;
           }
           return false;
       }
   };
   

3. 31. 下一个排列 - 力扣（LeetCode）;(涉及一个字典序算法)

   class Solution {
   public:
       void nextPermutation(vector<int>& nums) { 
           int n = nums.size(), i{n - 2};
           // 后向前遍历找(下标)相邻的升序对
           while (i >= 0) {
               if (nums[i] < nums[i + 1]) break; // 找到了
               --i;
           }
           if (i == -1) {
               reverse(nums.begin(), nums.end());
               return;
           }
           for (int j{n - 1}; j >= i + 1; --j)
               if (nums[i] < nums[j]) {
                   swap(nums[i], nums[j]);
                   reverse(nums.begin() + i + 1, nums.end());
                   break;
               }
       }
   };
   

   STL 的next_permutation实现:

   class Solution {
   public:
       void nextPermutation(vector<int>& nums) {
           auto first = nums.begin(), last = nums.end(), i = first;
           if (++i == last) // only 1 element
               return;
           i = last;
           --i;
           for (;;) {
               auto ii = i;
               --i;
               if (*i < *ii) {
                   auto j = last;
                   while (!(*i < *--j))
                       ;
                   iter_swap(i, j);
                   reverse(ii, last);
                   return;
               }
               if (i == first) {
                   reverse(first, last);
                   return;
               }
           }
       }
   };
   

4. 125. 验证回文串;剑指 Offer II 018. 有效的回文;

   class Solution {
   public:
       bool isPalindrome(string s) {
           int l{}, r = s.size() - 1;
           while (l < r) {
               while (l < r && (s[l] == ' ' || !isalnum(s[l]))) ++l;
               while (l < r && (s[r] == ' ' || !isalnum(s[r]))) --r;
               if (tolower(s[l]) == tolower(s[r]))
                   ++l, --r;
               else
                   return false;
           }
           return true;
       }
   };
   

5. 680. 验证回文串 II; 剑指 Offer II 019. 最多删除一个字符得到回文; 需要考虑不为回文之后, 删除哪个字符使之成为回文.

   class Solution {
   public:
       bool validPalindrome(string s) {
     int n = s.size(), l{}, r{n - 1};
     while (l < r && s[l] == s[r]) ++l, --r;
     auto f = [&](int l, int r) {
         while (l < r && s[l] == s[r]) ++l, --r;
         return l >= r;
     };
     return f(l + 1, r) || f(l, r - 1);
       }
   };
   

​

1. 1662. 检查两个字符串数组是否相等 - 力扣（LeetCode）;(虽然是简单题, 但是用双指针需要考虑越界等问题)

   class Solution {
   public:
       bool arrayStringsAreEqual(vector<string>& s, vector<string>& t) {
           int m = s.size(), n = t.size();
           int i{}, j{}, p{}, q{};
           while (i < m && j < n) {
               if (s[i][p++] != t[j][q++]) return false;
               if (p == s[i].size()) ++i, p = 0;
               if (q == t[j].size()) ++j, q = 0;
           }
           return i == m && j == n;
       }
   };
   

2. 1805. 字符串中不同整数的数目 - 力扣（LeetCode）;(常规双指针, 可暴力) 关键在于去除前导零.

   class Solution {
   public:
       int numDifferentIntegers(string s) {
           int n = s.size(), r{}, l{};
           unordered_set<string> st;
           for (;;) {
               while (l < n && !isdigit(s[l])) ++l; // 不是数字, 后移
               if (l == n) break;
               r = l;
               while (r < n && isdigit(s[r])) ++r;   // 一直是数字, 后移
               while (r - l > 1 && s[l] == '0') ++l; // 去除前导零, 这部分是重点
               st.insert(s.substr(l, r - l));
               l = r;
           }
           return st.size();
       }
   };
   // 
   class Solution {
   public:
       int numDifferentIntegers(string w) {
           int n = w.size();
           unordered_set<string> st;
           for (int i{}; i < n;) {
               while (i < n && !isdigit(w[i])) ++i;
               int r{i};
               while (r < n && isdigit(w[r])) ++r;
               while (i < r - 1 && w[i] == '0') ++i; // 去掉前导零
               if (r - i) st.insert(w.substr(i, r - i));
               i = r;
           }
           return st.size();
       }
   };
   

3. 1750. 删除字符串两端相同字符后的最短长度 - 力扣（LeetCode）;(常规双指针, 注意循环跳出的条件)

   class Solution {
   public:
       int minimumLength(string s) {
           int n = s.size(), r{n - 1}, l{};
           while (l < r && s[l] == s[r]) {
               // 去掉重复
               while (l < r && s[l] == s[l + 1]) ++l;
               while (l < r && s[r] == s[r - 1]) --r;
               ++l, --r;
           }
           return l <= r ? r - l + 1 : 0;
       }
   };
   

4. 165. 比较版本号; 与字符串中的整数不同, 这次需要直接取出整数而不是字符串, 所以也不用考虑前导零了(直接合并到整数中进行比较)

   class Solution {
   public:
       int compareVersion(string s, string t) {
           int m = s.size(), n = t.size(), i{}, j{}, x{}, y{};
           while (i < m || j < n) { // 都要比较
               x = 0, y = 0;
               // 先做减法防止溢出
               while (i < m && s[i] != '.') x = x * 10 - '0' + s[i++];
               while (j < n && t[j] != '.') y = y * 10 - '0' + t[j++];
               if (x != y) return x > y ? 1 : -1;
               ++i, ++j; // 略过'.'
           }
           return 0;
       }
   };
   

5. 392. 判断子序列 - 力扣（LeetCode）;(也可以DP, 但是双指针速度快)

   class Solution {
   public:
       bool isSubsequence(string s, string t) {
           int ns = s.size(), nt = t.size();
           int i{}, j{};
           while (i < ns && j < nt) {
               while (i < ns && j < nt && s[i] == t[j]) ++i, ++j;
               ++j;
           }
           return i == ns;
       }
   };
   

6. 38. 外观数列 - 力扣（LeetCode）;(经典双指针应用)

   class Solution {
   public:
       string countAndSay(int n) {
           auto f = [](string s) {
               int n = s.size(), l{1}, r{};
               string ans{};
               while (r < n) {
                   while (l < n && s[l] == s[r]) ++l;
                   ans += to_string(l - r) + s[r];
                   r = l++;
               }
               return ans;
           };
           string ans{"1"s};
           while (--n) ans = f(ans);
           return ans;
       }
   };
   

7. 844. 比较含退格的字符串; 关键点: 倒序遍历, 记录退格数量

   class Solution {
   public:
       bool backspaceCompare(string s, string t) {
           for (int i = s.size() - 1, j = t.size() - 1, bs{}, bt{};
                i >= 0 || j >= 0; --i, --j) {
               while (i >= 0)
                   if (s[i] == '#')
                       ++bs, --i;
                   else if (bs)
                       --bs, --i;
                   else
                       break;
               while (j >= 0)
                   if (t[j] == '#')
                       ++bt, --j;
                   else if (bt)
                       --bt, --j;
                   else
                       break;
               if (i >= 0 && j >= 0) {
                   if (s[i] != t[j]) return false;
               } else if (i >= 0 || j >= 0)
                   return false;
           }
           return true;
       }
   };
   

上难度

1. 1156. 单字符重复子串的最大长度;

2. 1023. 驼峰式匹配; (匹配问题)

3. 904. 水果成篮 - 力扣（LeetCode）;

4. 76. 最小覆盖子串 - 力扣（LeetCode）;

5. 42. 接雨水;(难)

原地操作

1. 27. 移除元素 - 力扣（LeetCode）;

   class Solution {
   public:
       int removeElement(vector<int>& nums, int val) {
           int n = nums.size(), l{};
           for (int r{}; r < n; ++r) {
               if (nums[r] != val) 
                   nums[l++] = nums[r];
           }
           return l;
       }
   };
   

2. 剑指 Offer 05. 替换空格 - 力扣（LeetCode）;(用到了27题的思想: 原地操作)

   class Solution {
   public:
       string replaceSpace(string s) {
           if (s.empty()) return s;
           int cnt{}, n = s.size();
           for (auto c : s) cnt += (c == ' ');
           int nn = n + 2 * cnt;
           s.resize(nn);
           for (int r{n - 1}; r >= 0; --r) { // 反着遍历
               if (s[r] != ' ') {
                   s[--nn] = s[r];
               } else {
                   s[--nn] = '0';
                   s[--nn] = '2';
                   s[--nn] = '%';
               }
           }
           return s;
       }
   };
   

3. $\bigstar$151. 反转字符串中的单词 - 力扣（LeetCode）;(原地算法, 比较经典的一类应用)

   class Solution {
   public:
       string reverseWords(string s) {
           reverse(s.begin(), s.end());
           int n = s.size(), idx{}; // idx 用于存放实际要挪到空字符位置的首索引
           for (int i{}; i < n; ++i) {
               if (s[i] == ' ') continue;
               int r{i};
               if (idx) s[idx++] = ' '; // 单词间的空格
               while (r < n && s[r] != ' ') s[idx++] = s[r++]; // 空字符补位
               reverse(s.begin() + idx - (r - i), s.begin() + idx);
               i = r; // 直接更新起始位置
           }
           s.erase(s.begin() + idx, s.end());
           return s;
       }
   };
   

4. 剑指 Offer 21. 调整数组顺序使奇数位于偶数前面;

   class Solution {
   public:
       vector<int> exchange(vector<int>& nums) {
           int n = nums.size(), l{};
           for (int r{}; r < n; ++r) {
               if (nums[r] & 1) swap(nums[l++], nums[r]);
           }
           return nums;
       }
   };
   

5. 905. 按奇偶排序数组;

   class Solution {
   public:
       vector<int> sortArrayByParity(vector<int>& nums) {
           int n = nums.size(), l{};
           for (int r{}; r < n; ++r) {
               if ((nums[r] & 1) == 0) swap(nums[l++], nums[r]);
           }
           return nums;
       }
   };
   //
   class Solution { //通解, 速度更快, 交换次数更少
   public:
       vector<int> sortArrayByParity(vector<int>& nums) {
           int l{}, r = nums.size() - 1;
           while (l < r) {
               while (l < r && (nums[l] & 1) == 0) ++l;
               // 遍历结束, l指向奇数
               while (l < r && (nums[r] & 1)) --r;
               // 遍历结束, r指向偶数
               if (l < r) swap(nums[l++], nums[r--]);
           }
           return nums;
       }
   };
   

6. 922. 按奇偶排序数组 II; 需要奇偶双指针, 找到不满足的才交换, 比较经典.

N数之和

第一题排序了也可以双指针, 但是还是遵循题目的意思吧.

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

   class Solution {
   public:
       vector<int> twoSum(vector<int>& nums, int target) {
           int n = nums.size(), l{}, r{n - 1};
           while (l < r) {
               int tmp{nums[l] + nums[r]};
               if (tmp == target)
                   return {l + 1, r + 1};
               else if (tmp > target)
                   --r;
               else
                   ++l;
           }
           return {-1, -1};
       }
   };
   

2. 2367. 算术三元组的数目; (可暴力, 不是严格意义上的N数之和, 但是可以应用三指针操作, 是最优解)

   class Solution {
   public:
       int arithmeticTriplets(vector<int>& nums, int diff) {
           int n = nums.size(), ans{}; // 三指针: 类似三数之和
           for (int i{}, j{1}, k{2}; i < n - 2 && j < n - 1 && k < n; ++i) {
               j = max(j, i + 1); // 保证j > i
               while (j < n - 1 && nums[j] - nums[i] < diff) ++j;
               if (j >= n - 1 || nums[j] - nums[i] > diff) continue;
               k = max(k, j + 1); // 与 j 同理
               while (k < n && nums[k] - nums[j] < diff) ++k;
               if (k < n && nums[k] - nums[j] == diff) ++ans;
           }
           return ans;
       }
   };
   

3. 15. 三数之和 - 力扣（LeetCode）;(经典的双指针问题, 需要去重)

   class Solution {
   public:
       vector<vector<int>> threeSum(vector<int>& nums) {
           sort(nums.begin(), nums.end());
           int n = nums.size();
           if (nums[0] > 0 || nums[n - 1] < 0)
               return {};
           if (nums[0] == 0 && 0 == nums[n - 1])
               return {{0, 0, 0}};
        
           vector<vector<int>> ans;
           ans.reserve(200);
           for (int i{}; i < n - 2; ++i) {
               if (i && nums[i] == nums[i - 1])
                   continue;
               for (int j{i + 1}, k{n - 1}; j < k;) {
                   int tmp = nums[i] + nums[j] + nums[k];
                   if (tmp == 0) {
                       ans.push_back({nums[i], nums[j], nums[k]});
                       ++j;
                       --k;
                       while (j < k && nums[j - 1] == nums[j])
                           ++j;
                       while (j < k && nums[k] == nums[k + 1])
                           --k;
                   } else if (tmp > 0) {
                       --k;
                   } else {
                       ++j;
                   }
               }
           }
           return ans;
       }
   };
   

4. 16. 最接近的三数之和 - 力扣（LeetCode）;

   class Solution {
   public:
       int threeSumClosest(vector<int>& nums, int target) {
           int n = nums.size(), ans = 1e7;
           sort(nums.begin(), nums.end());
           for (int i{}; i < n - 2; ++i) {
               int j{i + 1}, k{n - 1};
               while (j < k) {
                   int tmp{nums[i] + nums[j] + nums[k]};
                   if (tmp == target) return target; // 最优解
                   if (abs(tmp - target) < abs(ans - target)) ans = tmp;
                   tmp > target ? --k : ++j;
               }
           }
           return ans;
       }
   };
   

5. 18. 四数之和 - 力扣（LeetCode）;

   class Solution {
   public:
       vector<vector<int>> fourSum(vector<int> &nums, int target) {
           int n = nums.size();
           vector<vector<int>> ans;
           if (n < 4)
               return ans;
           sort(nums.begin(), nums.end());
        
           for (int i{}; i < n - 3; ++i) {
               if (i && nums[i - 1] == nums[i])
                   continue;
               for (int j{i + 1}; j < n - 2; ++j) {
                   if (j > i + 1 && nums[j] == nums[j - 1])
                       continue;
                   for (int p{j + 1}, q{n - 1}; p < q;) {
                       auto tmp = 0ll + nums[i] + nums[j] + nums[p] + nums[q];
                       if (tmp == target) {
                           ans.push_back({nums[i], nums[j], nums[p], nums[q]});
                           ++p, --q;
                           while (p < q && nums[p] == nums[p - 1])
                               ++p;
                           while (p < q && nums[q] == nums[q + 1])
                               --q;
                       } else if (tmp < target) {
                           ++p;
                       } else {
                           --q;
                       }
                   }
               }
           }
           return ans;
       }
   };
   

同向双指针(滑动窗口)

滑动窗口系列, 其实本质上还是双指针, 通过左右的两个指针确定滑动窗口的范围(左右边界), 然后进行操作.

方法:

1. 遍历右边界
2. 添加元素
3. 满足条件之后: 删除元素, 更新ans

1. 1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）;(处理两段可以做, 但是最优方法是滑窗, 正难则反, 思路转化, 直接找使和恰好为sum-x的情况)

   class Solution {
   public:
       int minOperations(vector<int>& nums, int x) {
           int target = accumulate(nums.begin(), nums.end(), 0) - x;
           if (target < 0) return -1;
           int n = nums.size(), ans{-1}, l{}, s{};
           for (int r{}; r < n; ++r) {
               s += nums[r];
               while (s > target) s -= nums[l++];
               if (s == target) ans = max(ans, r - l + 1);
           }
           return ans == -1 ? -1 : n - ans;
       }
   };
   

   使用双指针, 处理两段, 也可以做, 就是比较复杂, 也算一种通法.

   // 从左往右处理(先处理后缀)
   class Solution {
   public:
       int minOperations(vector<int>& nums, int x) {
           int n = nums.size(), s{}, r{n}; // [l,r)
           while (r > 0 && s + nums[r - 1] <= x) s += nums[--r];
           if (r == 0 && s < x) return -1;
           int ans = s == x ? n - r : n + 1;
           for (int l{}; l < n; ++l) {
               s += nums[l];
               while (r < n && s > x) s -= nums[r++];
               if (s > x) break;
               if (s == x) ans = min(ans, l + 1 + n - r);
           } // l + 1: 前缀长度, n - r: 后缀长度
           return ans > n ? -1 : ans;
       }
   };
   // 从右往左处理(先处理前缀)
        
   

2. 2379. 得到 K 个黑块的最少涂色次数 - 力扣（LeetCode）;

   class Solution {
   public:
       int minimumRecolors(string blocks, int k) {
           unordered_map<char, int> cnt{};
           int i{};
           for (; i < k; ++i) ++cnt[blocks[i]];
           int ans = k - cnt['B'];
           for (; i < blocks.size(); ++i) {
               --cnt[blocks[i - k]];
               ++cnt[blocks[i]];
               ans = min(ans, k - cnt['B']);
           }
           return ans;
       }
   };
   // 数组哈希
   class Solution {
   public:
       int minimumRecolors(string blocks, int k) {
           int cnt[2]{};
           int i{};
           for (; i < k; ++i) ++cnt[blocks[i] == 'B'];
           int ans = k - cnt[1];
           for (; i < blocks.size(); ++i) {
               --cnt[blocks[i - k] == 'B'];
               ++cnt[blocks[i] == 'B'];
               ans = min(ans, k - cnt[1]);
           }
           return ans;
       }
   };
   // 优化
   class Solution {
   public:
       int minimumRecolors(string blocks, int k) {
           int cnt[2]{}, ans{101};
           for (int i{}; i < blocks.size(); ++i) {
               if (i >= k) --cnt[blocks[i - k] == 'B'];
               ++cnt[blocks[i] == 'B'];
               ans = min(ans, k - cnt[1]);
           }
           return ans;
       }
   };
   

3. 219. 存在重复元素 II - 力扣（LeetCode）;(哈希映射map也可以做, 不过内存占用大)

   // 用哈希map, 朴素的想法
   class Solution {
   public:
       bool containsNearbyDuplicate(vector<int>& nums, int k) {
           unordered_map<int, int> st;
           for (int i{}; i < nums.size(); ++i) {
               auto it = st.find(nums[i]);
               if (it != st.end())
                   if (i - it->second <= k) return true;
               st[nums[i]] = i;
           }
           return false;
       }
   };
   

   滑窗+哈希集合: 相当于用一个固定大小的窗口(哈希集合)移动的过程记录满足条件的元素.

   class Solution {
   public:
       bool containsNearbyDuplicate(vector<int>& nums, int k) {
           unordered_set<int> st;
           for (int i{}; i < nums.size(); ++i) {
               if (i > k) st.erase(nums[i - k - 1]);
               if (st.count(nums[i])) return true;
               st.emplace(nums[i]);
           }
           return false;
       }
   };
   

4. 3. 无重复字符的最长子串 - 力扣（LeetCode）;

   class Solution {
   public:
       int lengthOfLongestSubstring(string s) {
           unordered_set<char> win{};
           int left{}, ans{};
           for (auto c : s) {
               while (win.find(c) != win.end()) win.erase(s[left++]);
               win.insert(c);
               ans = max(ans, (int)win.size());
           }
           return ans;
       }
   };
   

   只用STL来做, 比较慢(主要慢在遍历size()上), 下面改进一下, 用下标索引计算来更新ans.

   class Solution {
   public:
       int lengthOfLongestSubstring(string s) {
           unordered_set<char> win{};
           int left{}, ans{};
           for (int i{}; i < s.size(); ++i) {
               while (win.find(s[i]) != win.end()) win.erase(s[left++]);
               win.insert(s[i]);
               ans = max(ans, i - left + 1);
           }
           return ans;
       }
   };
   

   还不够快, 使用C-style数组代替哈希集合. 这里数组初始化用到了C++11的initializer_list, 比memset来的方便.

   class Solution {
   public:
       int lengthOfLongestSubstring(string s) {
           int n = s.size(), ans{}, l{};
           bool st[128]{};
           for (int r{}; r < n; ++r) {
               while (st[s[r]]) st[s[l++]] = false;
               ans = max(ans, r - l + 1);
               st[s[r]] = true;
           }
           return ans;
       }
   };
   

5. 1234. 替换子串得到平衡字符串 - 力扣（LeetCode）;

   两根指针指向窗口的左右边界.

   class Solution {
   public:
       int balancedString(string s) {
           int n = s.size(), m = n / 4, cnt[4]{};
           string t = "QWER";
           for (char c : s) ++cnt[t.find(c)];
           if (cnt[0] == m && cnt[1] == m && cnt[2] == m && cnt[3] == m)
               return 0;
           int ans = n;
           for (int r{}, l{}; r < n; ++r) {
               --cnt[t.find(s[r])];
               while (l <= r && cnt[0] <= m && cnt[1] <= m && cnt[2] <= m && cnt[3] <= m)
                   ans = min(ans, r - l + 1), ++cnt[t.find(s[l++])];
           }
           return ans;
       }
   };
   

   这里用到了一个不错的减少内存占用的方法, 就是把QWER四个字母计数映射到一个4元素的数组中, 通过find()方法实现.

6. 209. 长度最小的子数组 - 力扣（LeetCode）; 不错的题目, 有很多方法(当然最快的就是滑窗), 分别记录如下:

   • 暴力遍历(时间$n^2$空间$1$)
   • 前缀和+二分(时间$n\log n$空间$n$)
   • 滑窗(时间$n$空间$1$)

   // 暴力: 能过就行(更新测试数据集之后连C++都过不了了)
   class Solution {
   public:
       int minSubArrayLen(int target, vector<int>& nums) {
           int n = nums.size(), ans = INT_MAX;
           for (int l{}; l < n; ++l) {
               int win_len{}, win_sum{};
               for (int r{l}; r < n; ++r) {
                   ++win_len, win_sum += nums[r];
                   if (win_sum >= target) {
                       ans = min(win_len, ans);
                       break;
                   }
               }
           }
           return ans == INT_MAX ? 0 : ans;
       }
   };
   

   前缀和+二分:

   class Solution {
   public:
       int minSubArrayLen(int target, vector<int>& nums) {
           int n = nums.size(), ans = INT_MAX;
           vector<int> sums(n + 1);
           partial_sum(nums.begin(), nums.end(), sums.begin() + 1, plus<int>());
           for (int i{1}; i <= n; ++i) {
               auto it = lower_bound(sums.begin(), sums.end(), target + sums[i - 1]);
               if (it != sums.end())
                   ans = min(ans, static_cast<int>(it - sums.begin() - (i - 1)));
           }
           return ans == INT_MAX ? 0 : ans;
       }
   };
   

   因为这道题保证了数组中每个元素都为正，所以前缀和一定是递增的，这一点保证了二分的正确性。如果题目没有说明数组中每个元素都为正，这里就不能使用二分来查找这个位置了。

   作者：LeetCode-Solution

   滑窗:

   class Solution {
   public:
       int minSubArrayLen(int target, vector<int>& nums) {
           int n = nums.size(), ans = n + 1;
           int l{}, win_sum{};
           for (int r{}; r < n; ++r) {
               win_sum += nums[r];
               while (win_sum >= target)
                   ans = min(r - l + 1, ans), win_sum -= nums[l++];
           }
           return ans == n + 1 ? 0 : ans;
       }
   };
   

   或者:

   class Solution {
   public:
       int minSubArrayLen(int target, vector<int>& nums) {
           int n = nums.size(), ans{n + 1}, sum{}, l{};
           for (int r{}; r < n; ++r) {
               sum += nums[r];
               while (sum >= target) 
                   sum -= nums[l++], ans = min(ans, r - l + 2);
           }
           return ans == n + 1 ? 0 : ans;
       }
   };
   

7. 713. 乘积小于 K 的子数组 - 力扣（LeetCode）;

   class Solution {
   public:
       int numSubarrayProductLessThanK(vector<int>& nums, int k) {
           int n = nums.size(), ans{}, p{1}, l{};
           for (int r{}; r < n; ++r) {
               p *= nums[r];
               while (l <= r && p >= k) 
                   p /= nums[l++];
               ans += r - l + 1;
           }
           return ans;
       }
   };
   

8. 438. 找到字符串中所有字母异位词 - 力扣（LeetCode）;

   class Solution {
   public:
       vector<int> findAnagrams(string s, string p) {
           int n = s.size(), k = p.size();
           if (n < k) return {};
           vector<int> st(26), pt(26), ans{};
           // 计数器
           for (int i{}; i < k; ++i) ++st[s[i] - 'a'], ++pt[p[i] - 'a'];
           if (st == pt) ans.emplace_back(0);
           for (int i{}; i <= n - k; ++i) {
               --st[s[i] - 'a'];
               ++st[s[i + k] - 'a'];
               if (st == pt) ans.emplace_back(i + 1);
           }
           return ans;
       }
   };
   

   优化内存:

   class Solution {
   public:
       vector<int> findAnagrams(string s, string p) {
           int n = s.size(), k = p.size();
           if (n < k) return {};
           vector<int> ans{};
           int cnt[26]{};
           for (char c : p) ++cnt[c - 'a'];
           for (int r{}, l{}; r < n; ++r) {
               --cnt[s[r] - 'a'];
               while (cnt[s[r] - 'a'] < 0) ++cnt[s[l++] - 'a'];
               if (r - l + 1 == k) ans.emplace_back(l);
           }
           return ans;
       }
   };
   

9. 30. 串联所有单词的子串 - 力扣（LeetCode）;(上一题的进阶版)

10. 1163. 按字典序排在最后的子串;

​

哈希存值+滑动窗口

有序集合的妙用

1. 1438. 绝对差不超过限制的最长连续子数组 - 力扣（Leetcode）;(求长度)

   class Solution {
   public:
       int longestSubarray(vector<int>& nums, int limit) {
           int n = nums.size(), ans{};
           multiset<int> st;
           for (int r{}, l{}; r < n; ++r) {
               st.insert(nums[r]);
               while (*st.rbegin() - *st.begin() > limit)
                   st.erase(st.find(nums[l++]));
               ans = max(ans, r - l + 1);
           }
           return ans;
       }
   };
   

2. 不间断子数组 - 力扣 (LeetCode) 竞赛;(求数量)

   class Solution {
   public:
       long long continuousSubarrays(vector<int>& nums) {
           auto ans{0ll};
           int n = nums.size();
           multiset<int> st; // sorted
           for (int r{}, l{}; r < n; ++r) {
               st.insert(nums[r]);
               while (*--st.end() - *st.begin() > 2)
                   st.erase(st.find(nums[l++]));
               ans += r - l + 1;
           }
           return ans;
       }
   };
   

处理两段的滑动窗口

这类题目的数组两边都要记录, 可以先预处理出来左边, 然后对右边做滑动窗口.

1. 2516. 每种字符至少取 K 个;(需要处理两段, 不太好想)

2. 1574. 删除最短的子数组使剩余数组有序 - 力扣（Leetcode）;

3. 2565. 最少得分子序列 - 力扣（Leetcode）;

相向双指针

1. 647. 回文子串 - 力扣（LeetCode）;(中心扩展算法)

   class Solution {
   public:
       int countSubstrings(string s) {
           int n = s.size(), ans{};
           for (int i{}; i < n; ++i) {
               for (int j{}; j < 2; ++j) { // 奇偶两种中心
                   int l = i, r = i + j;
                   while (l >= 0 && r < n && s[l--] == s[r++])
                       ++ans;
               }
           }
           return ans;
       }
   };
   

2. 5. 最长回文子串;(中心扩展算法)

   class Solution {
   public:
       string longestPalindrome(string s) {
           if (s.empty()) return ""s;
           int n = s.size();
           auto expand = [&](int l, int r) { // 扩展中心
               while (l >= 0 && r < n && s[l] == s[r]) --l, ++r;
               return r - l - 1;
           };
           int start{}, end{};
           for (int i{}; i < n; ++i) {
               int l1 = expand(i, i);     // 单中心
               int l2 = expand(i, i + 1); // 双中心
               int len = max(l1, l2);
               // 更新中心`i`的左右端点
               if (len > end - start) start = i - (len - 1) / 2, end = i + len / 2;
           }
           return s.substr(start, end - start + 1);
       }
   };
   

3. 1813. 句子相似性 III - 力扣（LeetCode）;

   class Solution {
   public:
       bool areSentencesSimilar(string sentence1, string sentence2) {
           if (sentence1 == sentence2) return true;
           int n1 = sentence1.size(), n2 = sentence2.size();
           if (n1 < n2) swap(sentence1, sentence2), swap(n1, n2);
           int p1{};
           while (p1 < n2)
               if (sentence1[p1] == sentence2[p1]) {
                   p1++;
                   continue;
               } else
                   break;
           if (p1 == n2 && sentence1[p1] == ' ') return true;
           int q1{n1 - 1}, q2{n2 - 1};
           while (q2 >= 0)
               if (sentence1[q1] == sentence2[q2]) {
                   q1--, q2--;
                   continue;
               } else
                   break;
           if (q2 == -1 && sentence1[q1] == ' ') return true;
           return p1 > q2 && sentence2[q2 + 1] == ' ' && sentence1[q2 + 1] == ' ';
       }
   };
   

4. LCP 18. 早餐组合 - 力扣（LeetCode）;(可以哈希做, 但是还是双指针快)

   class Solution {
   public:
       const int MOD = 1e9 + 7;
       int breakfastNumber(vector<int>& staple, vector<int>& drinks, int x) {
           sort(drinks.begin(), drinks.end());
           sort(staple.begin(), staple.end());
           int i{}, j = drinks.size() - 1;
           long ans{};
           while (i < staple.size() && j >= 0) {
               if (staple[i] + drinks[j] <= x)
                   ++i, ans += (j + 1) % MOD;
               else --j;
           }
           return ans % MOD;
       }
   };
   

5. $\bigstar$1574. 删除最短的子数组使剩余数组有序;(经典题, 先处理一边, 然后处理另一边)

   // 先右后左
   class Solution {
   public:
       int findLengthOfShortestSubarray(vector<int>& arr) {
           int n = arr.size(), r{n - 1};
           // 右侧非递减
           while (r && arr[r - 1] <= arr[r]) --r;
           if (!r) return 0;
           int ans = r; // 删除r左边所有的数
        
           for (int l{}; !l || arr[l - 1] <= arr[l]; ++l) {
               while (r < n && arr[r] < arr[l]) ++r;
               ans = min(ans, r - l - 1);
           }
           return ans;
       }
   };
        
   // 先左后右
   class Solution {
   public:
       int findLengthOfShortestSubarray(vector<int>& arr) {
           int n = arr.size(), l{};
           // 左侧非递减
           while (l + 1 < n && arr[l] <= arr[l + 1]) ++l;
           if (l == n - 1) return 0;
           int ans = n - 1 - l; // 删除l右边所有的数
        
           for (int r{n - 1}; r == n - 1 || arr[r] <= arr[r + 1]; --r) {
               while (l >= 0 && arr[r] < arr[l]) --l;
               ans = min(ans, r - l - 1);
           }
           return ans;
       }
   };
   

6. 581. 最短无序连续子数组 - 力扣（LeetCode）;

   很经典的思路, 维护左右两边的最值.

快慢指针

快慢指针(链表中常用这种算法)

环形数组

457. 环形数组是否存在循环;

寻找重复数

287. 寻找重复数 - 力扣（LeetCode）;(用到了判圈算法)

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int f{}, s{};
        do f = nums[nums[f]], s = nums[s];
        while (f != s);
        f = 0;
        while (f != s) f = nums[f], s = nums[s];
        return s;
    }
};

删除重复项

需要用到原地修改方法, 多练就掌握了. 下面给出Python和C++两种实现, 包括一种通解的写法.

26. 删除有序数组中的重复项 - 力扣（LeetCode）;(经典的双指针题, 原地算法)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size(); 
        if (n < 2) return n;
        int l{}, r{1};
        while (r < n) {
            if (nums[l] != nums[r])
                nums[++l] = nums[r];
            ++r;
        }
        return 1 + l;
    }
};

80. 删除有序数组中的重复项 II - 力扣（LeetCode）;

可以通过快慢指针做, 个人感觉比较直观. 左指针指向重复的第一个数字, 右指针指向要删除的部分, 用右指针(重复之后出现的不同的数字)不断更新左指针的后一个位置即可. 代码如下:

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if (n := len(nums)) < 3:
            return n
        p1, p2 = 1, 2
        while p2 < n:
            if nums[p1 - 1] != nums[p2]:
                p1 += 1
                nums[p1] = nums[p2]
            p2 += 1
        return p1 + 1

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n < 3) return n;
        int l{1}, r{2};
        while (r < n) {
            if (nums[l - 1] != nums[r])
                nums[++l] = nums[r];
            ++r;
        }
        return 1 + l;
    }
};

下面是宫水三叶提供的通解.

【宫水三叶】关于「删除有序数组重复项」的通解 - 删除有序数组中的重复项 II - 力扣（LeetCode）;

针对删除超过重复次数为k的数字的通解.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        def process(k):
            idx = 0
            for num in nums:
                if idx < k or nums[idx - k] != num:
                    nums[idx] = num
                    idx += 1
            return idx
        return process(2)

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto f = [&](int k) {
            int idx{};
            for (int num: nums)
                if (idx < k || nums[idx - k] != num)
                    nums[idx++] = num;
            return idx;
        };
        return f(2);
    }
};

其实快慢指针也可以给出通解, 只不过需要修改的参数比较多:(看起来比较复杂)

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        def process(k):
            if (n := len(nums)) < k + 1:
                return n
            p1, p2 = k - 1, k
            while p2 < n:
                if nums[p1 - k + 1] != nums[p2]:
                    p1 += 1
                    nums[p1] = nums[p2]
                p2 += 1
            return p1 + 1
        return process(2)

C++版:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto f = [&](int k) {
            int n = nums.size();
            if (n < k + 1)
                return n;
            int l{k - 1}, r{k};
            while (r < n) {
                if (nums[l - k + 1] != nums[r])
                    nums[++l] = nums[r];
                ++r;
            }
            return 1 + l;
        };
        return f(2);
    }
};