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表的值作为返回值，返回
    }
}