【Leetcode_Hot100】哈希

是你亦然 / 2024-09-02 / 原文

哈希

1. 两数之和

49. 字母异位词分组

128. 最长连续序列

1. 两数之和

方法一：HashMap

在元素放入数组之前就进行判断，保证了不会取出同一个元素的情况,，例如[3,3]，如果先将数组中的所有元素放入hashMap，再判断是否存在，则返回结果为[1,1]，不符合题意。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        int[] res = new int[2];

        for(int i=0; i<nums.length; i++) {
            if(map.containsKey(target-nums[i])) {
                res[0] = i;
                res[1] = map.get(target-nums[i]);
                break;
            }
            map.put(nums[i], i);
        }

        return res;

    }
}

49. 字母异位词分组

方法一：HashMap

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        // map 记录 <key， stringList>
        Map<String, List<String>> map = new HashMap<>();

        for(String str : strs) {
            char[] array = str.toCharArray();
            Arrays.sort(array);

            // key 是 任意一个字符串 按字典序排列好的字符串
            String key = new String(array);
            // map中如果存在list则直接获取，否则需要新建一个list
            List<String> list = map.getOrDefault(key, new ArrayList<String>());
            list.add(str);
            map.put(key, list);
        }

        return new ArrayList<List<String>>(map.values());

    }
}

128. 最长连续序列

方法一：HashSet

先将数组中的元素放入Set集合中，再从nums[i]开始，依次判断下一个元素是否在set中，如果存在则tempLength加一，最后结果res为res和tempLength大中取大。

class Solution {
    public int longestConsecutive(int[] nums) {
        int res = 0;

        Set<Integer> set = new HashSet<>();

        for(int i=0; i<nums.length; i++) {
            set.add(nums[i]);
        }

        for(int i=0; i<nums.length; i++) {
            int currentNum = nums[i];
            int tempLength = 1;

            while(set.contains(currentNum+1)) {
                currentNum += 1;
                tempLength++;
            }

            res = Math.max(res, tempLength);
        }

        return res;
    }
}