【优选算法】（第七篇）
目录
⽔果成篮（medium）
题目解析
讲解算法原理
编写代码
找到字符串中所有字⺟异位词（medium）
题目解析
讲解算法原理
编写代码
⽔果成篮（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
你正在探访⼀家农场，农场从左到右种植了⼀排果树。这些树⽤⼀个整数数组fruits表⽰，其中fruits[i]是第i棵树上的⽔果种类。
你想要尽可能多地收集⽔果。然⽽，农场的主⼈设定了⼀些严格的规矩，你必须按照要求采摘⽔果：• 你只有两个篮⼦，并且每个篮⼦只能装单⼀类型的⽔果。每个篮⼦能够装的⽔果总量没有限制。• 你可以选择任意⼀棵树开始采摘，你必须从每棵树（包括开始采摘的树）上恰好摘⼀个⽔果。采
摘的⽔果应当符合篮⼦中的⽔果类型。每采摘⼀次，你将会向右移动到下⼀棵树，并继续采摘。• ⼀旦你⾛到某棵树前，但⽔果不符合篮⼦的⽔果类型，那么就必须停⽌采摘。
给你⼀个整数数组fruits，返回你可以收集的⽔果的最⼤数⽬。⽰例1：
输⼊：fruits=[1,2,1]输出：3
解释：
可以采摘全部3棵树。⽰例2：
输⼊：fruits=[0,1,2,2]输出：3
解释：
可以采摘[1,2,2]这三棵树。如果从第⼀棵树开始采摘，则只能采摘[0,1]这两棵树。
⽰例3：
输⼊：fruits=[3,3,3,1,2,1,1,2,3,3,4]输出：5
解释：
可以采摘[1,2,1,1,2]这五棵树。
讲解算法原理
解法（滑动窗⼝）：算法思路：
研究的对象是⼀段连续的区间，可以使⽤「滑动窗⼝」思想来解决问题。让滑动窗⼝满⾜：窗⼝内⽔果的种类只有两种。
做法：右端⽔果进⼊窗⼝的时候，⽤哈希表统计这个⽔果的频次。这个⽔果进来后，判断哈希表的⼤⼩：
▪ 如果⼤⼩超过2：说明窗⼝内⽔果种类超过了两种。那么就从左侧开始依次将⽔果划出窗
⼝，直到哈希表的⼤⼩⼩于等于2，然后更新结果；
▪ 如果没有超过2，说明当前窗⼝内⽔果的种类不超过两种，直接更新结果ret。
算法流程：
a. 初始化哈希表hash来统计窗⼝内⽔果的种类和数量；
b. 初始化变量：左右指针left=0，right=0，记录结果的变量ret=0；c. 当right⼩于数组⼤⼩的时候，⼀直执⾏下列循环：
i. 将当前⽔果放⼊哈希表中；
ii. 判断当前⽔果进来后，哈希表的⼤⼩：
• 如果超过2：
◦ 将左侧元素滑出窗⼝，并且在哈希表中将该元素的频次减⼀；◦ 如果这个元素的频次减⼀之后变成了0，就把该元素从哈希表中删除；◦ 重复上述两个过程，直到哈希表中的⼤⼩不超过2；
iii. 更新结果ret；
iv. right++，让下⼀个元素进⼊窗⼝；
d. 循环结束后，ret存的就是最终结果。
如图所示：
可以利用left和right双指针，此时需要一个统计数kinds去记录这个区间水果的种类，当kinds不超过2时right向右进行移动，便是利用hash思想，如果说超过便停止，此时移动left，这是只需要用双指针将整个数组遍历一遍（这里用数组不用hash是因为题目给的范围用数组会更高效，范围比较小如果用hash反而一直进出，时间复杂度会变高），那么整个题的时间复杂度便非常可观！
编写代码
c++算法代码（使用容器）：
class Solution
{
public:
int totalFruit(vector<int>& f)
{
unordered_map<int, int> hash; // 统计窗⼝内出现了多少种⽔果 int ret = 0;
for(int left = 0, right = 0; right < f.size(); right++)
{
hash[f[right]]++; // 进窗⼝
while(hash.size() > 2) // 判断
{
// 出窗⼝
hash[f[left]]--;
if(hash[f[left]] == 0)
hash.erase(f[left]);
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};c++算法代码（用数组模拟哈希表）：
class Solution
{
public:
int totalFruit(vector<int>& f)
{
int hash[100001] = { 0 }; // 统计窗⼝内出现了多少种⽔果
int ret = 0;
for(int left = 0, right = 0, kinds = 0; right < f.size(); right++)
{
if(hash[f[right]] == 0) kinds++; // 维护⽔果的种类
hash[f[right]]++; // 进窗⼝
while(kinds > 2) // 判断
{
// 出窗⼝
hash[f[left]]--;
if(hash[f[left]] == 0) kinds--;
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};java算法代码（使用容器）：
class Solution
{
public int totalFruit(int[] f)
{
Map<Integer, Integer> hash = new HashMap<Integer, Integer>(); // 统计窗⼝内⽔果的种类
int ret = 0;
for(int left = 0, right = 0; right < f.length; right++)
{
int in = f[right];
hash.put(in, hash.getOrDefault(in, 0) + 1); // 进窗⼝
while(hash.size() > 2)
{
int out = f[left];
hash.put(out, hash.get(out) - 1); // 出窗⼝
if(hash.get(out) == 0)
hash.remove(out);
left++;
}
// 更新结果
ret = Math.max(ret, right - left + 1);
}
return ret;
}
}java算法代码（用数组模拟哈希表）：
class Solution
{
public int totalFruit(int[] f)
{
int n = f.length;
int[] hash = new int[n + 1]; // 统计窗⼝内⽔果的种类
int ret = 0;
for(int left = 0, right = 0, kinds = 0; right < n; right++)
{
int in = f[right];
if(hash[in] == 0) kinds++; // 维护⽔果种类
hash[in]++; // 进窗⼝
while(kinds > 2) // 判断
{
int out = f[left];
hash[out]--; // 出窗⼝
if(hash[out] == 0) kinds--;
left++;
}
// 更新结果
ret = Math.max(ret, right - left + 1);
}
return ret;
}
}找到字符串中所有字⺟异位词（medium）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给定两个字符串s和p，找到s中所有p的异位词的⼦串，返回这些⼦串的起始索引。不考虑答案输出的顺序。
异位词指由相同字⺟重排列形成的字符串（包括相同的字符串）。
⽰例1:
输⼊:
s=)cbaebabacd),p=)abc)
输出:
[0,6]
解释:
起始索引等于0的⼦串是)cba),它是)abc)的异位词。
起始索引等于6的⼦串是)bac),它是)abc)的异位词。
⽰例2:
输⼊:
s=)abab),p=)ab)
输出:
[0,1,2]
解释:
起始索引等于0的⼦串是)ab),它是)ab)的异位词。
起始索引等于1的⼦串是)ba),它是)ab)的异位词。
起始索引等于2的⼦串是)ab),它是)ab)的异位词。
提⽰:
1<=s.length,p.length<=3*10^4
s和p仅包含⼩写字⺟
讲解算法原理
解法（滑动窗⼝+哈希表）：
算法思路：
◦ 因为字符串 p 的异位词的⻓度⼀定与字符串 p 的⻓度相同，所以我们可以在字符串 s 中构
造⼀个⻓度为与字符串 p 的⻓度相同的滑动窗⼝，并在滑动中维护窗⼝中每种字⺟的数量；◦ 当窗⼝中每种字⺟的数量与字符串 p 中每种字⺟的数量相同时，则说明当前窗⼝为字符串 p
的异位词；
◦ 因此可以⽤两个⼤⼩为 26 的数组来模拟哈希表，⼀个来保存 s 中的⼦串每个字符出现的个
数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。
编写代码
c++算法代码：
class Solution
{
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> ret;
int hash1[26] = { 0 }; // 统计字符串 p 中每个字符出现的个数
for(auto ch : p) hash1[ch - 'a']++;
int hash2[26] = { 0 }; // 统计窗⼝⾥⾯的每⼀个字符出现的个数
int m = p.size();
for(int left = 0, right = 0, count = 0; right < s.size(); right++)
{
char in = s[right];
// 进窗⼝ + 维护 count
if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
if(right - left + 1 > m) // 判断
{
char out = s[left++];
// 出窗⼝ + 维护 count
if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
}
// 更新结果
if(count == m) ret.push_back(left);
}
return ret;
}
};java算法代码：
class Solution
{
public List<Integer> findAnagrams(String ss, String pp)
{
List<Integer> ret = new ArrayList<Integer>();
char[] s = ss.toCharArray();
char[] p = pp.toCharArray();
int[] hash1 = new int[26]; // 统计字符串 p 中每⼀个字符出现的个数
for(char ch : p) hash1[ch - 'a']++;
int[] hash2 = new int[26]; // 统计窗⼝中每⼀个字符出现的个数
int m = p.length;
for(int left = 0, right = 0, count = 0; right < s.length; right++)
{
char in = s[right];
// 进窗⼝ + 维护 count
if(++hash2[in - 'a'] <= hash1[in - 'a']) count++;
if(right - left + 1 > m) // 判断
{
char out = s[left++];
// 出窗⼝ + 维护 count
if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;
}
// 更新结果
if(count == m) ret.add(left);
}
return ret;
}
}