C加加中在一串字符串中找出数字并数出数量

<think>嗯，用户让我用C++介绍一下滑动窗口的思想。首先，我需要确定用户对滑动窗口的理解程度。可能他们正在学习算法，或者遇到了相关问题，比如LeetCode上的题目。滑动窗口通常用于解决数组或字符串中的子串、子数组问题，比如找最长无重复字符的子串，或者求满足条件的子数组个数等。 我应该先解释滑动窗口的基本概念。比如，它是一种通过维护一个窗口来减少重复计算的技术，从而将时间复杂度从O(n²)优化到O(n)。需要区分两种类型：固定大小的窗口和可变大小的窗口。用户可能需要具体的例子来理解，比如固定大小的可以用数组中的连续k个元素的最大和，而可变大小的例子比如最长不重复子串。 接下来，可能需要给出代码示例。比如，固定窗口的例子，用循环计算初始窗口的和，然后滑动窗口逐个元素移动，更新当前和，并比较最大值。对于可变窗口，可能需要使用双指针，比如左指针和右指针，根据条件调整左指针的位置，同时记录窗口的最大长度。 还要注意边界条件的处理，比如数组为空，或者k值大于数组长度等情况。另外，要提到滑动窗口适用的场景，通常是在连续子数组或子字符串的问题中，当问题可以通过调整窗口的左右边界来高效解决的时候。 用户可能想知道为什么滑动窗口有效，所以需要解释其时间复杂度优势，比如避免了嵌套循环，通过左右指针各遍历一次数组，达到O(n)的时间复杂度。同时，可能需要提到与暴力解法的对比，突出其效率。 另外，可能需要提醒一些常见的错误，比如窗口的初始值设定不正确，或者移动指针时没有正确处理条件判断。例如，在可变窗口的例子中，如何更新左指针的位置，并确保窗口内的元素满足条件，比如没有重复字符。 最后，总结一下滑动窗口的应用场景和优势，让用户能够明确何时使用这种技术。可能还需要推荐一些练习题，比如LeetCode的题目编号，让用户可以通过实践加深理解。</think>### 滑动窗口算法思想（C++ 实现） #### 核心概念 滑动窗口是一种**双指针优化技术**，通过维护动态窗口区间减少重复计算，将嵌套循环优化为单层循环，时间复杂度通常从 O(n²) 降至 O(n)。 #### 两种典型应用场景 1. **固定窗口大小** 示例：求数组中长度为k的连续子数组最大和 2. **动态窗口大小** 示例：寻找字符串中最长无重复字符子串 --- ### 代码实现示例 #### 1. 固定窗口（求最大子数组和） ```cpp int maxFixedWindow(vector<int>& nums, int k) { if (nums.size() < k || k <= 0) return -1; int cur_sum = 0; for (int i = 0; i < k; ++i) { cur_sum += nums[i]; } int max_sum = cur_sum; for (int right = k; right < nums.size(); ++right) { cur_sum += nums[right] - nums[right - k]; // 滑动窗口核心操作 max_sum = max(max_sum, cur_sum); } return max_sum; } ``` #### 2. 动态窗口（最长无重复子串） ```cpp int lengthOfLongestSubstring(string s) { unordered_map<char, int> window; int left = 0, max_len = 0; for (int right = 0; right < s.size(); ++right) { char c = s[right]; window[c]++; // 出现重复时收缩左边界 while (window[c] > 1) { window[s[left]]--; left++; } max_len = max(max_len, right - left + 1); } return max_len; } ``` --- ### 算法特点 | 特征 | 说明 | |-------------|----------------------------------------------------------------------| | 时间复杂度 | O(n)，每个元素最多被访问两次（左右指针各一次） | | 空间复杂度 | O(1) 或 O(k)，取决于需要存储的窗口内容 | | 关键操作 | 窗口扩张（右指针移动）、窗口收缩（左指针移动） | --- ### 适用问题特征 1. 处理**连续子序列**问题（数组/字符串） 2. 需要跟踪窗口内的某种状态（和、频率、唯一性等） 3. 问题解的性质允许窗口单方向滑动 #### 典型练习题 - 最小覆盖子串（LeetCode 76） - 长度最小的子数组（LeetCode 209） - 字符串排列（LeetCode 567） 掌握滑动窗口的关键在于理解窗口收缩条件，通过合理维护窗口状态来避免重复计算，这是优化嵌套循环问题的有效手段。