hot100

哈希

（2025/7/5）

1两数之和

思路

这里写（copy）一点思路：
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。

代码

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();      //new 出来要加()
        int n = nums.length;
        for(int i = 0; i < n; ++i){
            if(hashtable.containsKey(target - nums[i])) {                       //实际的数字若在hashtable的key中
                return new int[]{hashtable.get(target - nums[i]), i};           //则输出
            }
            hashtable.put(nums[i], i);                                          //实际的数字不在key中，则存入<key,i>
        }
        return new int[0];
    }
}

49字母异位词分组

思路-1

由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。 

代码-1

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();    //map结构<String,List<String>>
        for(String str : strs){
            char[] array = str.toCharArray();
            Arrays.sort(array);
            String key = new String(array);
            List<String> list = map.getOrDefault(key, new ArrayList<String>()); //从map中提取key=key的list，没有则new空list
            list.add(str);                                                      //提出来的list，添加一个str
            map.put(key, list);                                                 //list存回map中的对应的key
            
        }
        return new ArrayList<List<String>>(map.values());                       //提取所有list，忽略key
    }
}

思路-2

可以将每个字母出现的次数使用字符串表示，作为哈希表的key。

代码-2

// 1. List 是接口，不能直接实例化
// Java 中，List 是一个接口（定义了列表的行为规范，但没有具体实现），而 ArrayList 是 List 接口的具体实现类（提供了列表的实际功能）。
// 接口本身不能直接创建对象（比如 new List<>() 是非法的），必须通过其实现类（如 ArrayList、LinkedList 等）来实例化。
// 2. 方法的返回类型是 List<List<String>>
// 方法 groupAnagrams 的返回类型声明为 List<List<String>>，这意味着：
// 返回值必须是 List 接口的实现类对象（如 ArrayList、LinkedList 等），因为接口不能直接返回。

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String str : strs){
            int[] count = new int[26];
            int length = str.length();
            for (int i = 0; i < length; i++ ){
                count[str.charAt(i) - 'a']++;                                   //将26个字母对应的个数存入count
            }
        StringBuffer sb = new StringBuffer();                                   //String不可更改，StringBuffer才可操作
        for(int i=0; i<26; i++){
            if(count[i] != 0)
            {
                sb.append((char)('a' + i));                                     //将字母和个数加入sb作为key，用append
                sb.append(count[i]);
            }
        }
        String key = sb.toString();                                             //StringBuffer转String
        List<String> list = map.getOrDefault(key,new ArrayList<String>());      //然后再取List
        list.add(str);                                                          //存List
        map.put(key,list);                                                      //将对应的key和值存入map
        }
        return new ArrayList<List<String>>(map.values());
    }
}

128最长连续序列

思路

直接存入Set，让其自动排序，并且顺序读取。

代码

class Solution {
   public int longestConsecutive(int[] nums) {
       Set<Integer> num = new HashSet<Integer>();       //create Set
       for(int n : nums){
        num.add(n);                                     //数组全部存入Set
       }

       int count = 0;

       for(int n : num){
        if(!num.contains(n - 1)){
            int curNum = n;                             //当前数字
            int curStreak = 1;                          //当前长度

            while(num.contains(curNum + 1)){
                curNum += 1;
                curStreak += 1;
            }

            count = Math.max(count, curStreak);         //最大长度交换
        }
       }
       return count;
       
   }
}

总结

总体上将数组存入HashMap或者Set，然后遍历，判断是否满足条件，满足则计数，不满足则跳过。