双指针

不含重复字符的最长子字符串 原题链接：https://leetcode.cn/problems/wtcaE1/ 给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度。 1.静态滑动窗口11

字符串中的变位词 原题链接：https://leetcode.cn/problems/MPnaiL/ 给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的某个变位词。第一个字符串的排列之一是第二个字符串的 子串 。 1.静态滑动窗口1由于知道目标字符串的长度，故可以通过暴力枚举的方式（一个静态的滑动窗口）来枚举出所有的情况， 并对枚举的每种情况进行字母数量的统计，利用哈希表实现字母数量的统计， 123456789101112131415class Solution {public: bool checkInclusion(string pattern, string text) { for (int i = 0, j = i + pattern.length(); j <= text.length(); ++i, ++j) { int flag = 0; vector<int> cnt(26); for (int k = 0; k < pattern.length(); ++k) cnt[pattern[k] - 'a']++;//查找目标的字母数量统计 for (int k = i; k < j; ++k) cnt[text[k] - 'a']--;//遍历的字符串的字母数量统计 for (int i = 0; i < 26; ++i) if (cnt[i] != 0) flag = 1;//判断字母数量是否相同 if (flag) continue; return true; } return false; }}; 勉强能过，时间复杂度与空间复杂度都很高。 2.静态滑动窗口2对每次的字母数量判断操作进行修改，对边界值进行加入与减出操作，思路没有问题的，先做记录在此。 1234567891011121314151617181920212223class Solution {public ...

字符串中的所有变位词 原题链接：https://leetcode.cn/problems/VabMRr/ 给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。 变位词 指字母相同，但排列不同的字符串。 1.静态滑动窗口11

0和1个数相同的子数组 原题链接：https://leetcode.cn/problems/A1NYOS/ 给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。 1.暴力枚举123456789101112131415class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; for (int j = 0; j < nums.size(); ++j) { int sum = 0; for (int i = j; i >= 0; --i) { if (nums[i] == 1) sum++; else sum--; if (sum == 0) ans = max(ans, j - i + 1); } } return ans; }}; 程序超时，看来这题对时间复杂度的要求很高，需要牺牲空间复杂度换时间复杂度降低。 2.前缀和+哈希 在预处理前缀和时，将 nums[i] 为 0 的值当做 −1 处理 从而将问题转化为：如何求得最长一段区间和为 0 的子数组，使用哈希表来记录某个前缀和出现的最小下标是多少。 12345678910111213141516171819202122class Solution {public: int findMaxLength(vector<int>& nums) { int ans = 0; int len = nums.size(); //1.前缀和数组初始化 int *prefix = new int[len + 10](); for (int i = 1; i <= nums.size(); ++i) prefix[i] = pref ...

和为k的子数组 原题链接：https://leetcode.cn/problems/QTMn0o/ 给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数， 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len < nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int n = i; n < j; ++n) sum += nums[n]; if (sum == k) ans++; } } return ans; }}; 所有用例成功输出结果，但由于时间复杂度太高，导致程序超时， 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出边界值，尝试更新答案： 1234567891011121314151617class Solution {public: int subarraySum(vector<int>& nums, int k) { int ans = 0; for (int len = 1; len <= nums.size(); ++len) { int sum = 0; for (int i = 0; i < len; ++i) sum += n ...

和大于等于target的最短子数组 原题链接：https://leetcode.cn/problems/2VG8Kg/ 给定一个含有 n 个正整数的数组和一个正整数 target ， 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。 如果不存在符合条件的子数组，返回 0 。 1.静态滑动窗口1遍历滑动窗口大小，每次for循环滑动窗口大小值固定，每次对滑动窗口中的内容进行求和，尝试更新答案，时间超时： 1234567891011121314151617181920class Solution {public: int minSubArrayLen(int target, vector<int>& nums) { int flag = 0; int ans = nums.size(); //遍历滑动窗口的大小 for (int len = 1; len <= nums.size(); ++len) { for (int i = 0, j = i + len; j <= nums.size(); ++i, ++j) { int sum = 0; for (int k = i; k < j; ++k) sum += nums[k]; if (sum >= target && len <= ans) { ans = len; flag = 1; } } } if (!flag) return 0; return ans; }}; 2.静态滑动窗口2遍历滑动窗口大小，每次for循环滑动窗口大小值固定， 维护一个sum值 进行加入与减出，每次窗口移动加入与减出 ...

乘积小于K的子数组 原题链接：https://leetcode.cn/problems/ZVAVXX/ 1.静态滑动窗口 维护一个mul乘积 对乘积进行 * / 操作 当是当滑动窗口的长度len 非常大时， 乘积mul可能会超出数据范围 如果多个 0 ~ 1000 范围的num[i]相乘 可能超出 int 数据范围 这种方法非常容易超出int的数据范围 认定为失败的方法 123456789101112131415161718class Solution {public: int numSubarrayProductLessThanK(vector<int>& nums, int k) { if (k == 0) return 0; int ans = 0; //遍历滑动窗口的长度 for (int len = 1; len <= nums.size(); ++len) { int mul = 1; int flag = 1; for (int i = 0; i < len; ++i) mul *= nums[i]; if (mul < k) ans++; for (int i = 1; i + len <= nums.size(); ++i) { mul /= nums[i - 1]; mul *= nums[i + len - 1]; if (mul < k) ans++; } } return ans; }}; 2.动态滑动窗口 从前往后处理所有的nums[i]，使用变量i、j代表窗口的左右端点（静态窗口弊端完美解决），使用变量mul记录当前窗口的乘积， 当 mul>=k 时，我们考虑将左端点i右移，同时消除左端点元素 nums[i] 对 mul 的贡献，直到mul>=k不再满足 这样就可以得到每个右端点 nums[i] 的最远左端 ...

排序数组中两个数字之和 原题链接：https://leetcode.cn/problems/kLl5u1/ 给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。 函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer[0] < answer[1] < numbers.length 。 假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。 1.双指针1234567891011121314151617181920class Solution {public: vector<int> twoSum(vector<int>& numbers, int target) { vector<int> ans; int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { ans.push_back(low); ans.push_back(high); break; } else if (sum < target) { low++; } else if (sum > target) { high--; } } return ans; }}; 时间复杂度：$O(n)$ 空间复杂度：$O(1)$ 2.二分查找12345678910111213141516171819202122class S ...

数组中和为0的三个数 原题链接：https://leetcode.cn/problems/1fGaJU/ 1.暴力法暴力法虽然测试用例能正确输出，但是程序时间复杂度太高直接超时， 123456789101112131415161718192021222324252627class Solution {public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> ans; sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; //使用双指针解决剩余两个数字 for (int j = i + 1; j < nums.size(); ++j) { for (int k = j + 1; k < nums.size(); ++k) { if (nums[i] + nums[j] + nums[k] == 0) { //判定符合要求的答案是否重复 //ans.push_back({nums[i], nums[j], nums[k]}); if (ans.size() == 0) ans.push_back({nums[i], nums[j], nums[k]}); else { int flag = 1; for (in ...

双指针算法 1.算法模板1234for (int i = 0, j = 0; i < n; i ++ ) { while (j < i && check(i, j)) j ++; /*具体问题逻辑*/} 常见双指针问题： 对于一个序列，用两个指针维护一段区间 对于两个序列，维护某种次序，比如归并排序中合并两个有序序列的操作 2.双指针练习（1）AcWIng799.最长连续不重复子序列方法1：暴力法1234567891011121314151617181920212223242526272829#include<iostream>using namespace std;const int MAX = 100010;int n;int a[MAX], mark[MAX];bool check(int low, int high) { for (int i = low + 1; i <= high; ++i) { for (int j = low; j < i; ++j) { if (a[i] == a[j]) return false; } } return true;}int main() { int res = 0; cin >> n; for (int i = 0; i < n; ++i) scanf("%d", &a[i]); for (int i = 0; i < n; ++i) { for (int j = 0; j <= i; ++j) { if (check(j, i)) res = max(res, i - j + 1); } } cout << res << endl; return 0;} 方法2：双指针法仔细考虑暴力法就会发现，暴力法在解题时有很多地方是重复计算了： 比如 j = 0，i ...