文章目录一、两数之和解题思路代码实现及解析总结二、面试题 01.02. 判定是否互为字符重排解题思路三、字母异位词分组解题思路代码实现及解析总结一、两数之和Leetcode链接给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。你可以假设每种输入只会对应一个答案并且你不能使用两次相同的元素。你可以按任意顺序返回答案。解题思路暴力解法的遍历方法一般是固定一个数往后遍历来匹配。但是固定一个数往前遍历去与之匹配也完全是可以覆盖所有情况的。之所以介绍这种方法是因为它与哈希表的使用非常适配将固定过的元素放入哈希表而“往前遍历”这个操作就可以变为去哈希表中找哈希表放的都是之前固定过的的元素这样往前查找操作的时间复杂度就会变为O(1)。代码实现及解析classSolution{publicint[]twoSum(int[]nums,inttarget){MapInteger,IntegermapnewHashMap();for(inti0;inums.length;i){intkeytarget-nums[i];if(map.containsKey(key)){//前面找到了匹配值returnnewint[]{i,map.get(key)};}map.put(nums[i],i);//把该元素添加到Map中}returnnewint[]{-1,-1};}}总结复习解题思路中的往前遍历操作与哈希表的适配性二、面试题 01.02. 判定是否互为字符重排Leetcode链接给定两个由小写字母组成的字符串 s1 和 s2请编写一个程序确定其中一个字符串的字符重新排列后能否变成另一个字符串。仅说明简单解题思路解题思路一道经典的题目我们发现只要两个字符串中字母出现的个数是相等的就符合题意。所以我们先把第一个字符串丢入数组模拟的哈希表中统计出现次数然后直接遍历第二个字符串在哈希表将对应字母hash[字母]–同时判断此时哈希表中该位置是否减为0若不是则说明不符合题意也可以直接在开头判断两字符串长度是否相同进行优化。还有一种方法就是对字符串进行排序看是排序后否相等这个方法在下一题会有大用处三、字母异位词分组Leetcode链接给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。示例 :输入: strs [“eat”, “tea”, “tan”, “ate”, “nat”, “bat”]输出: [[“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”]]解释在 strs 中没有字符串可以通过重新排列来形成 “bat”。字符串 “nat” 和 “tan” 是字母异位词因为它们可以重新排列以形成彼此。字符串 “ate” “eat” 和 “tea” 是字母异位词因为它们可以重新排列以形成彼此。解题思路HashMap的一种巧妙用法遇到分组问题时将分组所用到的判断条件与存储该条件所对应元素的容器绑定起来。而且我们发先在这种情况下使用的判断条件一般只能是具有标识性的“key”值然后使用containsKey()来判断所以传统的 if(…) 语句来判断条件在这里就不适用了。这样直接就可以在哈希表中找到对应条件并得到相应容器将元素放入其中最后还可以使用map.values()将所有的分组都提取出来。如果按以前的做法用if语句来判断进行多轮分组就可能需要多次重复遍历数组每次遍历就只能进行一次分组。那所以在本题中我们用到的判断条件“key”值就是将字符串排序之后得到的同一组字符串所具有的唯一的标识。代码实现及解析classSolution{publicListListStringgroupAnagrams(String[]strs){MapString,ListStringmapnewHashMap();for(Stringstr:strs){char[]tmpstr.toCharArray();Arrays.sort(tmp);//排序StringkeynewString(tmp);if(!map.containsKey(key)){//如果不存在此分组就创建这种新的分组map.put(key,newArrayListString());}map.get(key).add(str);//将str放入对应分组依靠的就是排序后的标识性的key值}returnnewArrayListListString(map.values());}}总结复习解题思路中Map在分组问题上的巧用