hot100-一刷-01哈希(共3道题)

1.两数之和

题目链接

题目描述

代码实现

分析：

• 暴力的话就是两个for循环依次寻找相加为target的两个数。
• 用一个map记录已经遍历过的数，其中key就用这个数的字面值，value就存它的下标。
  判断是否相加为taget的时候，只需要看map中是否有target-nums[i]就可以，说明当前的nums[i]和之前遍历的那个数相加就是我们要找的数。

代码：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++){
            if(map.containsKey(target - nums[i])){
                return new int[]{i, map.get(target - nums[i])} ;
            }
            map.put(nums[i], i);
        }
        return new int[2];
    }
}

49.字母异位词分组

题目链接

题目描述

代码实现

分析：

• 排序，对每个str内部的字符进行排序，排序后作为key。则必然有顺序不同但字符个数相同的字符串才有相同的key

代码：

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<>();
        for (String str : strs){
            // 对每个str内部的字符进行排序，排序后作为key
            // 则必然有顺序不同但字符个数相同的字符串才有相同的key
            char[] chars = str.toCharArray();
            Arrays.sort(chars);
            // 排序后的字符串做为key
            String key = new String(chars);
            List<String> value = map.getOrDefault(key, new ArrayList<String>());
            value.add(str);
            map.put(key, value);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

附加

在Java中，遍历Map的所有键（keys）的方法

• 使用keySet()

  Map<String, Integer> map = new HashMap<>();
  // 假设这里已经向map添加了一些元素
  
  for (String key : map.keySet()) {
  	System.out.println("Key: " + key);
  }
  

• 使用entrySet()与增强的for循环

  Map<String, Integer> map = new HashMap<>();
  // 假设这里已经向map添加了一些元素
  
  for (Map.Entry<String, Integer> entry : map.entrySet()) {
  	String key = entry.getKey();
  	System.out.println("Key: " + key);
  }
  

128. 最长连续序列

题目链接

题目描述

代码实现

思路：
对于x，x+1，..., x+y, 如果直接暴力， 则会重复计算，比如下一次计算x+2的时候，又会开始算x+3，...， x+y，但是， 这个结果一定小于x加到y的，所以只需要判断我当前是否是从这个连续数组的最开头开始的。即，有没有x-1项，有就再看x-1前，有没有（x-1） -1项...， 没有x-1项，说明当前就是最开头的。少了很多中间无意义的计数。
代码：

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> numsSet = new HashSet<>();
        // Set去重
        for(int num : nums){
            numsSet.add(num);
        }

        // 记录最大长度
        int res = 0;

        for(int num : numsSet){
            // x 没有x-1 才开始算，有的话直接跳过
            // 假设有比x小的， x-1， 那后面遍历到x-1的时候 在循环里会计算(x-1) +1
            if(!numsSet.contains(num - 1)){
                int curNum = num;
                int cnt = 1;
                while(numsSet.contains(curNum + 1)){
                    cnt++;
                    curNum++;
                }
                res = Math.max(res, cnt);
            }
        }
        return res;
    }
}