目录

⽔果成篮（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;
 }
}