常见面试题——滑动窗口算法

按奇偶排序数组

题目理解

题目链接：按奇偶排序数组

简而言之就是把数组中所有偶数移到前面，奇数移到后面，返回任意满足条件的数组即可。

解题思路

双指针交换
用两个指针l（从0开始）和r（从l+ 1 开始）遍历数组：

• 当 r 指向的是偶数，且 l 指向的是奇数 → 交换两者
• 当 l 指向的是偶数 → l 右移（保证l左侧都是偶数）
• r 不断右移遍历整个数组

代码详解

classSolution{public:vector<int>sortArrayByParity(vector<int>&nums){intn=nums.size();if(n==1){// 数组长度为1，直接返回returnnums;}intl=0;// 左指针，指向待交换的奇数位置intr=l+1;// 右指针，遍历数组找偶数while(r<n){// 右指针是偶数、左指针是奇数 → 交换if((nums[r]%2==0)&&(nums[l]%2==1)){swap(nums[r],nums[l]);}// 左指针是偶数 → 右移，扩大已排序的偶数区域if(nums[l]%2==0){l++;}r++;// 右指针继续遍历}returnnums;}};

找到字符串中所有字母异位词

题目理解

题目链接：找到字符串中所有字母异位词

给定字符串s和p，找出 s 中所有是 p 的**字母异位词的子串，返回这些子串的起始索引。
（字母异位词：字母相同但排列不同的字符串**）

解题思路

滑动窗口 + 哈希计数

因为只涉及小写字母，用两个长度为 26 的数组（hash1、hash2）分别统计 p 的字母频率、s 滑动窗口内的字母频率。通过维护一个count变量，记录窗口中有效匹配的字母数（即窗口中该字母的数量 ≤ p 中该字母的数量），当count 等于 p的长度时，说明当前窗口是 p 的异位词。

代码详解

classSolution{public:vector<int>findAnagrams(string s,string p){vector<int>ret;// 存储结果的起始索引inthash1[26]={0};// 统计p的字母频率// 第一步：初始化p的字母频率数组for(autoch:p){hash1[ch-'a']++;}inthash2[26]={0};// 统计滑动窗口内的字母频率intcount=0;// 记录窗口中有效匹配的字母数intp_len=p.size();// p的长度，用于窗口大小控制// 滑动窗口：r是右指针，l是左指针for(intl=0,r=0;r<s.size();r++){charcur=s[r];// 右指针扩大窗口：将当前字符加入hash2if(++hash2[cur-'a']<=hash1[cur-'a']){count++;// 该字符在p中且数量未超，有效匹配数+1}// 窗口大小超过p的长度，左指针缩小窗口if(r-l+1>p_len){charout=s[l++];// 左指针右移，弹出窗口左端字符if(hash2[out-'a']--<=hash1[out-'a']){count--;// 弹出的字符是有效匹配的，有效匹配数-1}}// 有效匹配数等于p的长度，说明当前窗口是异位词if(count==p_len){ret.push_back(l);// 记录起始索引l}}returnret;}};