【C++】优选算法必修篇之双指针实战：水果成篮 & 找到字符串中所有字母异位词

我不是呆头

发布于 2025-12-20 14:36:27

应用场景

应用场景链接直达请点击<----------

1. 水果成篮

1.1 题目链接

题目链接直达请点击<----------

1.2 题目描述

1.3 题目示例

1.4 算法思路

我们通过阅读题目，可以将题目转化成一句更通俗的化：找出连续的最长的子数组长度，里面最多包含两种不同类型的水果（此处为数组中不同的数据）。
我们就可以采用一段滑动窗口解决，right指针向右探索，并用哈希hash来记录每种水果出现的次数。（进窗口）

我们右指针向右探索的时候，将种类的个数映射到哈希表里面

unordered_map<int, int> hash;  // 开始时完全为空

// 当我们执行：
hash[1]++;  // 创建键值对：key=1, value=1
hash[2]++;  // 创建键值对：key=2, value=1  
hash[3]++;  // 创建键值对：key=3, value=1

// 此时哈希表里只有3个元素：
// 键1 → 值1
// 键2 → 值1  
// 键3 → 值1

cout << hash.size(); // 输出3，因为确实有3个键值对

当我们通过求哈希表的size()来判断种类是否大于2，如果大于2就需要进行出窗口操作，先将当前左指针指向的种类个数–，然后判断它是不是为0，为0就使用erase删除（不管是否为0都进行执行后进行下一步，left++，然后继续判断）

执行完while循环后说明种类已经减少到题目要求范围内，然后我们就可以进行更新结果，然后继续进窗口。当right走到数组尽头截止for循环，返回结果。

1.5 核心代码

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> hash;//一个int类型的Key对应一个int类型的val
        int left = 0, right = 0, ret = 0;
        for(right = 0; right < fruits.size(); right++)
        {
            hash[fruits[right]]++;//进窗口——key（种类）++
            while(hash.size() > 2) //判断——水果种类数>2
            {
                hash[fruits[left]]--;//出窗口，种类--
                if(hash[fruits[left]] == 0)//同一类减到0，从水果中删除这个种类
                    hash.erase(fruits[left]);
                    left++;
            }
            ret = max(ret,right-left+1);
        }
        return ret;
    }
};

1.6 示例测试（总代码）

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int, int> hash;//一个int类型的Key对应一个int类型的val
        int left = 0, right = 0, ret = 0;
        for (right = 0; right < fruits.size(); right++)
        {
            hash[fruits[right]]++;//进窗口——key（种类）++
            while (hash.size() > 2) //判断——水果种类数>2
            {
                hash[fruits[left]]--;//出窗口，种类--
                if (hash[fruits[left]] == 0)//同一类减到0，从水果中删除这个种类
                    hash.erase(fruits[left]);
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

int main()
{
    vector<int> nums1 = { 1,2,3,2,2 };
    int result = Solution().totalFruit(nums1);
    cout << result << endl;

    return 0;
}

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

2.1 题目链接

题目链接直达请点击<----------

2.2 题目描述

2.3 题目示例

2.4 算法思路

首先我们可以利用哈希和滑动窗口，先把p的每个字符遍历丢进哈希表1里面，记录个数，然后再以p的字符串长度为范围固定滑动窗口的大小然后开始遍历s并丢尽哈希表2里面，来对比他们这个长度范围内的字符种类的个数，相同的话就是异位词返回左指针，然后都++向右遍历找第二个；不相同也是向右找第一个和第二个。

大但是我们每次窗口滑动后都要完整比较两个哈希表的全部26个位置，但实际上每次滑动只改变了两个字符，这种"用大炮打蚊子"的方式造成了大量冗余比较。那我们可以通过什么方法优化呢？
我们引入count来跟踪窗口内的有效字符（和p中相同的字符）的个数。

我们右指针向右探索，先将这个字符的个数++，然后与p中字符个数相比较，到l长度范围内就停止探索（进窗口先停止）。如果小于等于p中的字符个数就count++。

然后判断当前的范围是否超过p的len，如果超过就要进行出窗口，先将左指针指向的数据出现的次数与这个字符出现在p中的次数相比较，然后把出窗字符在hash2中的计数减1，如果小于等于就让count--。

最后如果count == len,就将最左指针指向的数据尾插到一个容器中，然后寻找下一个所有。

2.5 核心代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;//存储索引
        int hash1[26] = {0};
        int len = p.size();
        for(auto ch:p) hash1[ch-'a']++;//统计p中的每个字符的个数

        int hash2[26] = {0};//用来统计窗口中每个字符出现的字数
        for(int left = 0,right = 0,count = 0;right< s .size();right++ )
        {
            char in = s[right];//进窗口的字符
            if(++hash2[in-'a'] <= hash1[in-'a']) count++;//进窗口，维护count
            if(right - left + 1 > len)
            {
                char out = s[left++];//出窗口的字符
                if(hash2[out-'a']-- <= hash1[out-'a']) count--;
            }
            if(count == len) ret.push_back(left);
        }
        return ret;
    }
};

2.6 示例测试（总代码）

#include<iostream>
#include<unordered_map>
#include<vector>
using namespace std;

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ret;//存储索引
        int hash1[26] = { 0 };
        int len = p.size();
        for (auto ch : p) hash1[ch - 'a']++;//统计p中的每个字符的个数

        int hash2[26] = { 0 };//用来统计窗口中每个字符出现的字数
        for (int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];//进窗口的字符
            if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;//进窗口，维护count
            if (right - left + 1 > len)
            {
                char out = s[left++];//出窗口的字符
                if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
            }
            if (count == len) ret.push_back(left);
        }
        return ret;
    }
};

int main()
{
    string s = "cbaebabacd";
    string p = "abc";

    vector<int> result = Solution().findAnagrams(s, p);

 
    cout << "[";
    for (int i = 0; i < result.size(); i++) {
        cout << result[i];
        if (i < result.size() - 1) cout << ",";
    }
    cout << "]" << endl;

    return 0;
}