当前位置： 首页 > news >正文

[刷题总结] 双指针 滑动窗口

news 2025/4/7 12:39:49

🌻个人主页：路飞雪吖~-CSDN博客

目录

一、双指针

1.题目：283. 移动零 - 力扣（LeetCode）

2.题目：1089. 复写零 - 力扣（LeetCode）

3.题目：202. 快乐数 - 力扣（LeetCode）

4.题目：11. 盛最多水的容器 - 力扣（LeetCode）

5.题目：611. 有效三角形的个数 - 力扣（LeetCode）

6.题目：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

7.题目：15. 三数之和 - 力扣（LeetCode）

8.题目：18. 四数之和 - 力扣（LeetCode）

二、滑动窗口

1.题目：209. 长度最小的子数组 - 力扣（LeetCode）

2.题目：3. 无重复字符的最长子串 - 力扣（LeetCode）

3.题目：1004. 最大连续1的个数 III - 力扣（LeetCode）

4.题目：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

5.题目：904. 水果成篮 - 力扣（LeetCode）

6.题目：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

7.题目：30. 串联所有单词的子串 - 力扣（LeetCode）

8.题目：76. 最小覆盖子串 - 力扣（LeetCode）

一、双指针

常见两种形式：

<1> 对撞指针：

• 从两端向中间移动

• 一般用于顺序结构中

• 终止条件：两个指针相遇或错开

<2> 快慢指针

• 使用两个移动速度不同的指针在数组或链表等序列结构上移动

• 常用：慢的指针向后移动⼀位，⽽快的指针往后移动两位，实现⼀快⼀慢

注意：将数组的内容分成左右两部 分。这种类型的题，⼀般就是使⽤「双指针」来解决。

1.题目：283. 移动零 - 力扣（LeetCode）

思路： <双指针>

• 定义两个指针

• right != 0，进行交换 swap( left, right); 使得[0 , left]的这个区间全部都是非零的区间；

• left++;

class Solution {
public:void moveZeroes(vector<int>& nums) {for(int left = 0, right = 0; right < nums.size(); right++){if(nums[right] != 0){swap(nums[left], nums[right]);left++;}}}
};

2.题目：1089. 复写零 - 力扣（LeetCode）

正难则反，从前往后覆盖不行，就从后往前。

（1）异地求解（新开数组）

class Solution {
public:void duplicateZeros(vector<int>& arr) {// 异地操作 新开数组int n = arr.size();vector<int> newArr; // 初始化空数组for (int num : arr) {if (newArr.size() >= n) break; // 长度足够时提前终止if (num == 0) {newArr.push_back(0); // 添加第一个0if (newArr.size() < n) // 检查是否还能添加第二个0newArr.push_back(0);} else  newArr.push_back(num); // 非零元素直接添加}arr = newArr; // 将结果复制回原数组}
};

（2）双指针（原地）

先根据“异地”操作，然后优化成双指针下的“就地”操作

<1> 先找到最后一个“复写”的数（模拟一遍往后）

     • 先判断 cur 位置的值

     • 决定 dest 向后移动一步或者两步

     • 判断一下 dest 是否已经到结束为止

     • cur++

     • (处理边界情况)

<2> "从后往前"完成复写操作

class Solution {
public:void duplicateZeros(vector<int>& arr) {// 1、先找到最后一个“复写”的数int dest = -1, cur = 0, n = arr.size();while(cur < n){if(arr[cur]) dest++;else dest += 2;if(dest >= n - 1) break;cur++;}// 处理边界情况if(dest == n){arr[n - 1] = 0;cur--;dest -= 2;}// 从后往前复写while(cur >= 0){if(arr[cur]) arr[dest--] = arr[cur--];else {arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

3.题目：202. 快乐数 - 力扣（LeetCode）

（类似链表成环问题）快慢指针

class Solution {
public:int bitSum(int n){int sum = 0;while(n){int  t =n % 10;// 取最后一个数sum += t * t;// 把数据存入n = n / 10;// 去掉最后一个数}return sum;}bool isHappy(int n) {// 快慢指针int slow = n, fast = bitSum(n);// fast在第二个位置while(slow != fast){slow = bitSum(slow);// slow走一步fast = bitSum(bitSum(fast));// fast走两步}return slow == 1;// 判断相遇位置是否等于1}
};

4.题目：11. 盛最多水的容器 - 力扣（LeetCode）

class Solution {
public:int maxArea(vector<int>& height) {int left = 0, right = height.size() - 1, ret = 0;while(left < right){int V = min(height[left], height[right]) * (right - left);// 求出体积ret = max(ret, V);//  每次取较大的体积数// 移动指针if(height[left] <= height[right]) left++; else right--;}return ret;;}
};

5.题目：611. 有效三角形的个数 - 力扣（LeetCode）

class Solution {
public:int triangleNumber(vector<int>& nums) {// 优化sort(nums.begin(), nums.end());// 双指针int n = nums.size();int ret = 0;// 记录有效个数for(int i = n - 1; i >= 2; i--)// 固定最大的数{int left = 0, right = i - 1;// left固定的第一个数，right固定的第二个数while(left < right){if(nums[left] + nums[right] > nums[i])// a + b > c 符合条件{ret += right - left;// 在符合条件的区间right--;// 统计完符合的区间后，减小区间，接着下一轮统计}elseleft++;// 不符合条件，++到下一个数寻找}}return ret;}
};

6.题目：LCR 179. 查找总价格为目标值的两个商品 - 力扣（LeetCode）

class Solution {
public:vector<int> twoSum(vector<int>& price, int target) {int n = price.size();int left = 0, right = n - 1;while(left < right){int sum = price[left] + price[right];if(sum < target) left++;if(sum > target) right--;if(sum == target)return {price[left], price[right]};}return {};}
};

7.题目：15. 三数之和 - 力扣（LeetCode）

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {vector<vector<int>> ret;// 排序sort(nums.begin(), nums.end());// 双指针int n = nums.size();for(int i = 0; i < n;)// 固定数 a{int left = i + 1, right = n - 1, target = -nums[i];while(left < right){int sum = nums[left] + nums[right];if(sum > target) right--;else if(sum < target) left++;else // sum == target{ret.push_back({nums[i], nums[left], nums[right]});// 把符合条件的数据存入left++, right--; // 不漏// 去重 left  rightwhile(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}// 去重 ii++;while(i < n && nums[i] == nums[i - 1]) i++;            }return ret;}
};

8.题目：18. 四数之和 - 力扣（LeetCode）

与"三数之和"类似，四数之和固定两个数。

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> ret;// 排序sort(nums.begin(), nums.end());// 双指针int n = nums.size();for(int i = 0; i < n;)// 固定一个数a{for(int j = i + 1; j < n;)// 固定一个数b{int left = j + 1, right = n - 1;while(left < right){long long dest = (long long)target - nums[i] - nums[j];long long sum = nums[left] + nums[right];if(sum > dest) right--;else if(sum < dest) left++;else // sum == target{// 保存数据ret.push_back({nums[i], nums[j], nums[left], nums[right]});left++, right--;// 不漏//去重 left rightwhile(left < right && nums[left] == nums[left - 1]) left++;while(left < right && nums[right] == nums[right + 1]) right--;}}// 去重 jj++;while(j < n && nums[j] == nums[j - 1]) j++;}// 去重 ii++;while(i < n && nums[i] == nums[i - 1]) i++;}return ret;}
};

二、滑动窗口

滑动窗口，即一个区间左右滑动。

• left = 0, right = 0;

• 进窗口 

• 判断 

• 出窗口 

• 更新结果 

1.题目：209. 长度最小的子数组 - 力扣（LeetCode）

利用单调性（规避了很多没有必要的枚举行为），使用“同向指针”来进行优化。

• left = 0, right = 0;

• 进窗口 （sum += nums[right];）

• 判断  (sum >= target;)

• 出窗口 (left++;)

• 更新结果 ( min(len, right - left + 1);)

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size(), sum = 0, len = INT_MAX;for(int left = 0, right = 0; right < n; right++){sum += nums[right];// 进窗口while(sum >= target)// 判断{len = min(len, right - left + 1);// 更新结果sum -= nums[left];left++;// 出窗口}}return len == INT_MAX ? 0 : len;}
};

2.题目：3. 无重复字符的最长子串 - 力扣（LeetCode）

hash + 滑动窗口：

• left = 0, right = 0;

• 进窗口 （让字符进入hash表 hash[s[right]]++;）

• 判断 （窗口内是否出现重复字符 hash[s[right]] > 1;）

        出窗口 （从hash表中删除该字符 hash[s[left++]]--;）

• 更新结果 （len = max(len, right - left + 1);）

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size(), len = 0;int hash[128] = { 0 };for(int left = 0, right = 0; right < n; right++){hash[s[right]]++;// 进窗口while(hash[s[right]] > 1)// 判断hash[s[left++]]--;// 出窗口len = max(len, right - left + 1);// 更新结果}return len;}
};

3.题目：1004. 最大连续1的个数 III - 力扣（LeetCode）

滑动窗口：

• left = 0, right = 0;

• 进窗口

        如果为1，无视

        如果为0，计数器+1

• 判断 （zero > k）

        出窗口

• 更新结果

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size(), len = 0, zero = 0;for(int left = 0, right = 0; right < n; right++){if(nums[right] == 0) zero++;// 进窗口while(zero > k)// 判断if(nums[left++] == 0) zero--;// 出窗口len = max(len, right -left + 1);// 更新结果}return len;}
};

4.题目：1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

🌟正难则反！！！  ----转化为--->  求最长子串

• target = sum[nums] - x; // target 为最长子串数的和

• len 为最长子数的个数

• left = 0, right = 0;

• 进窗口 sumLR += nums[right]

• 判断  sumLR > target  (不符合，要出窗口)

• 出窗口 sumLR -= nums[left++];

• 更新结果 sum == target

class Solution {
public:int minOperations(vector<int>& nums, int x) {int n = nums.size(), sum = 0;for(auto e : nums) sum += e;int target = sum - x;int len = -1;if(target < 0) return -1;for(int left = 0, right = 0, sumLR = 0; right < n; right++){sumLR += nums[right];//进窗口while(sumLR > target)// 判断sumLR-= nums[left++];// 出窗口if(sumLR == target)// 更新结果len = max(len, right - left + 1);}if(len == -1) return -1;else return n - len;}
};

5.题目：904. 水果成篮 - 力扣（LeetCode）

✨ hash + 滑动窗口

• left = 0, right = 0;

• 进窗口 hash[f[right]]++;

• 判断 hash.size() > 2

• 出窗口 hash[f[left]]--; (要判断该位置是否为0)

• 更新结果

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> hash;int n = fruits.size(), len =0;for(int left = 0, right = 0; right < n; right++){hash[fruits[right]]++;// 进窗口while(hash.size() > 2)// 判断{hash[fruits[left]]--;if(hash[fruits[left]] == 0)// 树上无水果，删除hash.erase(fruits[left]);left++;}len = max(len , right - left + 1);// 更新结果}return len;}
};

6.题目：438. 找到字符串中所有字母异位词 - 力扣（LeetCode）

• left = 0, right = 0, count = 0; // count 记录进入hash2的字符数

• 进窗口  hash2[ in ]++;// 判断count是否需要++

• 判断  right - left + 1 > p.size(); // >出窗口

• 出窗口  hash2[ out ]--;

• 更新结果 check( count == p.size());// 直接使用 check(hash2, hash1) --> 大量数据时，使得时间复杂度高

        利用变量count来统计窗口中“有效字符”的个数；

        进窗口后： 判断 hash2[in] <= hash1[in] --> count++;

        出窗口前： 判断 hash2[out] <= hash1[out] --> count--;

        更新结果： count == p.size();

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int hash1[26] = { 0 };for(auto ch : p) hash1[ch - 'a']++;// 记录p中字符出现的个数int hash2[26] = { 0 };// 记录sint n = p.size();for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];hash2[in - 'a']++;// 进窗口if(hash2[in -'a'] <= hash1[in - 'a']) count++;// 维护countif(right - left + 1 > n)// 判断{char out = s[left++];// 出窗口if(hash2[out - 'a'] <= hash1[out - 'a']) count--;hash2[out - 'a']--;// 把表中的数据去掉}// 更新结果if(count == n) ret.push_back(left);}return ret;}
};

7.题目：30. 串联所有单词的子串 - 力扣（LeetCode）

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1;for(auto& string : words) hash1[string]++;int len = words[0].size(), m = words.size();for(int i = 0; i < len; i++)// 执行 len 次{unordered_map<string, int> hash2;for(int left = i, right = i, count = 0; right + len < s.size(); right += len)// 每次移动 len 个长度{string in = s.substr(right, len);// 截取 一个单词的长度hash2[in]++;// 进窗口if(hash2[in] <= hash1[in]) count++;// 维护 countif(right - left + 1 > m * len)// 判断{string out = s.substr(left, len);// 出窗口if(hash2[out] <= hash1[out]) count--;// 维护counthash2[out]--;left += len;// 每次移动 len 个长度}if(count == m) ret.push_back(left);}}return ret;}
};

8.题目：76. 最小覆盖子串 - 力扣（LeetCode）

• left = 0, right = 0, count = 0;

• 进窗口 hash[in]++;

• 判断 count == kinds

        进窗口之后： 当 hash2[in] == hash1[in]  --> count++;

        出窗口前：当 hash2[out] == hash1[out] --> count--;

        判断条件 count == kinds

• 更新结果 --> 起始位置，最短长度

• 出窗口 hash2[out]--;

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = { 0 };// 统计 t 中每一个字符出现的频次int kinds = 0;// 统计有效字符有多少种for(auto ch : t)if(hash1[ch]++ == 0) kinds++;int hash2[128] = { 0 };// 统计窗口内每个字符的频次int minlen = INT_MAX, begin = -1;for(int left = 0, right = 0, count = 0; right < s.size(); right++){char in = s[right];hash2[in]++;// 进窗口if(hash2[in] == hash1[in]) count++;// 维护countwhile(count == kinds)// 判断{if(right - left + 1 < minlen)//更新结果 {minlen = right - left + 1;begin = left;}char out = s[left++];// 出窗口if(hash2[out] == hash1[out]) count--;hash2[out]--;}}if(begin == -1) return "";else return s.substr(begin, minlen);}
};


http://www.mrgr.cn/news/97362.html

相关文章：

  • 【内网安全】DHCP 饿死攻击和防护
  • Gerapy二次开发：用户管理专栏主页面开发
  • 【ARTS】【LeetCode-2873】有序三元组中的最大值!
  • CSS快速上手
  • 手撕LLM（二）：从源码出发，探索LoRA加载、推理全流程
  • CentOS Linux升级内核kernel方法
  • rust 同时处理多个异步任务，并在一个任务完成退出
  • 毕业设计：实现一个基于Python、Flask和OpenCV的人脸打卡Web系统（六）
  • Nginx 生产配置文件
  • 数据分析-Excel-学习笔记Day1
  • TYUTJava阶段测试
  • 新一代AI架构实践：数字大脑AI+智能调度MCP+领域执行APP的黄金金字塔体系
  • java发送http请求
  • k8s 1.23升级1.24
  • k8s之Ingress讲解
  • TDengine 从入门到精通（2万字长文）
  • 线程池/内存池/mysql连接池
  • 15分钟完成Odoo18.0安装与基本配置
  • Nginx 常见面试题
  • 现代Web表单验证的终极解决方案：构建可扩展的企业级验证系统