【优选算法】（第三十篇）
目录
存在重复元素II（easy）
题目解析
讲解算法原理
编写代码
字⺟异位词分组（medium）
题目解析
讲解算法原理
编写代码
存在重复元素II（easy）
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个整数数组nums和⼀个整数k，判断数组中是否存在两个不同的索引i和j，满⾜nums[i]==nums[j]且abs(i-j)<=k。如果存在，返回true；否则，返回false。
⽰例1：
输⼊：nums=[1,2,3,1],k=3
输出：true
⽰例2：
输⼊：nums=[1,0,1,1],k=1
输出：true
讲解算法原理
解法（哈希表）：
算法思路：
解决该问题需要我们快速定位到两个信息：
• 两个相同的元素；
• 这两个相同元素的下标。
因此，我们可以使⽤「哈希表」，令数组内的元素做 key 值，该元素所对应的下标做 val 值，将「数组元素」和「下标」绑定在⼀起，存⼊到「哈希表」中。
思考题：
如果数组内存在⼤量的「重复元素」，⽽我们判断下标所对应的元素是否符合条件的时候，需要将不同下标的元素作⽐较，怎么处理这个情况呢？
答：这⾥运⽤了⼀个「⼩贪⼼」。
我们按照下标「从⼩到⼤」的顺序遍历数组，当遇到两个元素相同，并且⽐较它们的下标时，这两个下标⼀定是距离最近的，因为：
• 如果当前判断符合条件直接返回 true ，⽆需继续往后查找。
• 如果不符合条件，那么前⼀个下标⼀定不可能与后续相同元素的下标匹配（因为下标在逐渐变
⼤），那么我们可以⼤胆舍去前⼀个存储的下标，转⽽将其换成新的下标，继续匹配。
编写代码
c++算法代码：
class Solution
{
public:
bool containsNearbyDuplicate(vector<int>& nums, int k)
{
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++)
{
if(hash.count(nums[i]))
{
if(i - hash[nums[i]] <= k) return true;
}
hash[nums[i]] = i;
}
return false;
}
};java算法代码：
class Solution
{
public boolean containsNearbyDuplicate(int[] nums, int k)
{
Map<Integer, Integer> hash = new HashMap<>();
for(int i = 0; i < nums.length; i++)
{
if(hash.containsKey(nums[i]))
{
if(i - hash.get(nums[i]) <= k) return true;
}
hash.put(nums[i], i);
}
return false;
}
}字⺟异位词分组（medium）
从这道题我们可以拓展⼀下视野，不要将容器局限于基本类型，它也可以是⼀个容器嵌套另⼀个容器的复杂类型。
题目解析
1.题目链接：. - 力扣（LeetCode）
2.题目描述
给你⼀个字符串数组，请你将字⺟异位词组合在⼀起。可以按任意顺序返回结果列表。字⺟异位词是由重新排列源单词的字⺟得到的⼀个新单词，所有源单词中的字⺟通常恰好只⽤⼀次。⽰例1:
输⼊:strs=["eat","tea","tan","ate","nat","bat"]输出:[["bat"],["nat","tan"],["ate","eat","tea"]]
讲解算法原理
解法（哈希表+排序）：
算法思路：
互为字⺟异位词的单词有⼀个特点：将它们「排序」之后，两个单词应该是「完全相同」的。所以，我们可以利⽤这个特性，将单词按照字典序排序，如果排序后的单词相同的话，就划分到同⼀
组中。
这时我们就要处理两个问题：
• 排序后的单词与原单词需要能互相映射；
• 将排序后相同的单词，「划分到同⼀组」；
利⽤语⾔提供的「容器」的强⼤的功能就能实现这两点：• 将排序后的字符串（ string ）当做哈希表的 key 值；• 将字⺟异位词数组（ string[] ）当成 val 值。
定义⼀个「哈希表」即可解决问题。
编写代码
c++算法代码：
class Solution
{
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
unordered_map<string, vector<string>> hash;
// 1. 把所有的字⺟异位词分组
for(auto& s : strs)
{
string tmp = s;
sort(tmp.begin(), tmp.end());
hash[tmp].push_back(s);
}
// 2. 结果提取出来
vector<vector<string>> ret;
for(auto& [x, y] : hash)
{
ret.push_back(y);
}
return ret;
}
};java算法代码：
class Solution
{
public List<List<String>> groupAnagrams(String[] strs)
{
Map<String, List<String>> hash = new HashMap<>();
// 1. 先把所有的字⺟异位词分组
for(String s : strs)
{
char[] tmp = s.toCharArray();
Arrays.sort(tmp);
String key = new String(tmp);
if(!hash.containsKey(key))
{
hash.put(key, new ArrayList());
}
hash.get(key).add(s);
}
// 2. 提取结果
return new ArrayList(hash.values());
}
}