当前位置：首页 > article >正文

【专项刷题】— 哈希表

article 2024/11/15 3:20:33

1、两数之和 - 力扣（LeetCode）

思路：

使用哈希表，将每次x = target - nums[i]，查看哈希表中是否含有这个x值

代码：

public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        Map<Integer,Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++){
            int x = target - nums[i];
            if(hash.containsKey(x)){
                return new int[]{i, hash.get(x)};
            }
            //没有就继续添加到哈希表
            hash.put(nums[i],i);
        }
        //照顾编译器
        return new int[]{-1,-1};
    }

2、判定是否互为字符重排 - 力扣（LeetCode）

思路：
先判断两个字符串的长度，长度不相等直接返回false
用一个数组表示的哈希表，先添加s1的字符，再遍历s2直接减去当前字符的值，然后再判断一下，如果出现小于零的数，就说明两个字符串有不相等的字符，返回false
代码：
public boolean CheckPermutation(String s1, String s2) {
        if(s1.length() != s2.length()){
            return false;
        }
        int[] hash = new int[26];
        //将s1中的字符添加到哈希表中
        for(int i= 0; i < s1.length(); i++){
            hash[s1.charAt(i) - 'a']++;
        }
        //将s2添加到哈希表中，顺便减去相同字符的值，小于0就返回
        for(int i = 0; i < s2.length(); i++){
            hash[s2.charAt(i) - 'a']--;
            if(hash[s2.charAt(i) - 'a'] < 0){
                return false;
            }
        }
        return true;
    }

3、存在重复元素 II - 力扣（LeetCode）

思路：
将数据存储在哈希表中，遍历数组，遍历到一个数就在哈希表中查找是否有当前数
有的话就开始进行判断，没有的话就添加到哈希表
代码：
public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Map<Integer,Integer> hash = new HashMap<>();
        for(int i = 0; i < n; i++){
            if(hash.containsKey(nums[i])){
                int a = hash.get(nums[i]);
                if(Math.abs(a - i) <= k){
                    return true;
                }
            }
            hash.put(nums[i],i);
        }
        return false;
    }

4、字母异位词分组 - 力扣（LeetCode）

思路：
首先将字符串数组里面的字符分组，然后将它们排序
然后遍历数组的时候判断一下key，创建一个key，这个可以都是已经排序好的了，检查哈希表中是否有这个key
有的话就就将原字符添加到顺序表中，没有的话就添加到哈希表中，创建顺序表
代码：
public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hash = new HashMap<>();
         
        //先给字符串数组分组，然后每组字符都排序
        for(String s : strs){
            char[] tmp = s.toCharArray();
            //排序
            Arrays.sort(tmp);
            //创建key,这里面的字符串都是已经排序的
            String key = new String(tmp);

            //判断
            if(! hash.containsKey(key)){
                hash.put(key,new ArrayList());
            }
            //把原字符添加到数组中
            hash.get(key).add(s);
        }
        return new ArrayList(hash.values());
    }

查看全文

http://www.kler.cn/a/289253.html