【优选算法】（第三十篇）
目录
存在重复元素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());}
}