LeetCode-哈希表专题

1.两数相加

1. two-sum(easy)
   Leetcode

解法1：双重循环

class Solution {
    public int[] twoSum(int[] nums, int target) {

        for(int i=0;i<nums.length;i++){
            int temp = target - nums[i];
            for(int j=i+1;j<nums.length;j++){
                if(temp == nums[j]){
                    return new int[]{i,j};
                }
            }
        }
        return new int[]{};
    }
}

解法2：利用HashMap，将值作为key，索引作为value，存入Map，
循环遍历数组，当Map中的key是target-nums[i]的值的时候，返回当前的i和那个key的value

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

2.存在重复元素

217. contains-duplicate(easy)
     Leetcode

解法1：HashMap，判断是否包含当前值的key

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

解法2：HashSet，直接比较结束后的Set长度和nums的长度

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet s = new HashSet();
        for(int i=0;i<nums.length;i++){
            s.add(nums[i]);
        }
        return s.size()<nums.length;
    }
}

3.最长和谐序列

594. Longest Harmonious Subsequence (Easy)
     Leetcode

解法1：双重循环
解法2：将数组放到hashMap中，扫描一遍HashMap

class Solution {
    public int findLHS(int[] nums) {
        HashMap<Integer,Integer> m = new HashMap();
        for(int num : nums){
            m.put(num, m.getOrDefault(num, 0) + 1);
        }
        int res = 0;
        for(int key : m.keySet()){
            if(m.containsKey(key+1)){
                res = Math.max(res,m.get(key)+m.get(key+1));
            }
        }
        return res;
    }
}