LeetCode Hot 100 题解[java版本，冲大厂]

LeetCode Hot 100 题解[java版本，冲大厂]

1. 两数之和

题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

思路：

使用HashMap构建哈希表，然后需要注意一下里面的键值对。

每遍历一个元素，看看 hashMap 中是否存在满足要求的目标数字。

注意查询的时候，查询的是target - nums[i]

时间复杂度为O(n),空间复杂度也为O（n)

代码：

class Solution {public int[] twoSum(int[] nums, int target) {//哈希表思路HashMap<Integer, Integer> map = new HashMap<>();int n = nums.length;for(int i = 0; i < n; i++){if(map.containsKey(target - nums[i])){return new int[]{map.get(target - nums[i]), i};}else{map.put(nums[i], i);}}return new int[]{};}
}

2. 字母异位词分组

题目描述

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

思路：

属于hash表的题目，只不过需要注意一下，传入hash里面的键值对的形式。

传入的键是排序好的字符；传入的值是没有排序的字符的list表

每次遍历字符串数组得到的字符串，先对其进行排序，排序之后，在将其插入hash表中

注意hash表中一个比较好的用法就是getOrDefault，如果没有，我们就new一个新的ArrayList

最后面，hash的值就是我们要返回的数据，可以直接使用values()方法获取到hash表当中的值

代码：

class Solution {public List<List<String>> groupAnagrams(String[] strs) {//对每个字符串进行排序,排序完之后，加入hash表HashMap<String, ArrayList<String>> map = new HashMap<>();for(String str : strs){char ch[] = str.toCharArray();      //先转化为字符数组，方便排序Arrays.sort(ch);                    //排序String compare = new String(ch);    //再转化为string，方便hash表比较ArrayList<String> list = map.getOrDefault(compare, new ArrayList<String>());list.add(str);map.put(compare, list);             //将新的list插入hash表}return new ArrayList<>(map.values());   //将hash表的值作为返回值，返回}
}