刷题「哈希表」相关

数组中两个数的和为给定值（简单）

暴力算法在这里就不讲了。

这里介绍下用「哈希表」来解决此题。

为什么会想到哈希表呢？这是因为

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap map = new HashMap();
        for(int i = 0; i < nums.length; i++) {
            int n = target - nums[i];
            if(map.containsKey(n)) {
                return new int[] {(int) map.get(n), i};
            }
            map.put(nums[i], i);
        }
        throw new IllegalArgumentException("null");
    }
}

复杂度分析：

时间复杂度：O()。

空间复杂度：O()。

判断数组是否含有重复元素（简单）

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashMap<Integer, Integer> hashmap = new HashMap<>();
        for (int i = 0; i < nums.length; ++ i) {
            if (hashmap.containsKey(nums[i])) {
                return true;
            }
            hashmap.put(nums[i], null);
        }
        return false;
    }
}

复杂度分析：

时间复杂度：O()。

空间复杂度：O()。

最长和谐序列（简单）

class Solution {
    public int findLHS(int[] nums) {
        int ret = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();

        for (int num : nums) {
            hashMap.put(num, hashMap.getOrDefault(num, 0) + 1);
        }

        for (int key : hashMap.keySet()) {
            if (hashMap.containsKey(key + 1)) {
                ret = Math.max(ret, hashMap.get(key) + hashMap.get(key + 1));
            }
        }

        return ret;
    }
}