哈希表三种数据结构在leetcode中的使用情况分析

数组作为哈希表

数组大小确定范围

有效的字母异位词

class Solution {
    public boolean isAnagram(String s, String t) {
        //hashmap double*
        if(s.length()!=t.length())
        {
            return false;
        }
        int n=s.length();
        int[] ans=new int[26];
        for(int i=0;i<n;i++)
        {
            ans[s.charAt(i)-'a']++;
        }
        for(int i=0;i<n;i++)
        {
            ans[t.charAt(i)-'a']--;
        }
        for(int i=0;i<26;i++)
        {
            if(ans[i]>0)
            {
                return false;
            }
        }
        return true;
       
    }
}

这道题问a包不包含b，且都是小写字母，我们就可以用数组来存放需要被包含的b，下标就用s.charAt(). 

赎金信

跟上道题一模一样的思路

set作为哈希表

没有规定数值的大小，需要判断数据是否重复出现过 

两个数组的交集

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        //特殊情况返回空数组
        if(nums1.length==0 ||nums2.length==0)
        {
            return new int[0];
        }

        //求交集，用HashSet存放
        Set<Integer> bc1=new HashSet<>();
        Set<Integer> bc2=new HashSet<>();

        for(int i:nums1)
        {
            bc1.add(i);
        }
        for(int i:nums2)
        {
            if(bc1.contains(i))
            {
                bc2.add(i);
            }
        }
        int[] ans=new int[bc2.size()];
        int j=0;
        for(int i:bc2)
        {
            ans[j++]=i;
        }
        return ans;
    }
}

这道题数值没有大小范围不适合用数组，且题意明确是找出交集，哪怕两个数组里都有n个数字9，最终也只需要输出一个数字9，就很适合用set作为哈希表，遍历完两个数组就知道了交集。

快乐数

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> cnt=new HashSet<>();
        while(!cnt.contains(n))
        {
            cnt.add(n);
            n=sum(n);
        }
        return n==1;
    }

    private int sum(int x)
    {
        int record=0;
        while(x>0)
        {
            int temp=x%10;
            record+=temp*temp;
            x/=10;
        }
        return record;
    }
}

这道题数值没有固定大小，肯定要排除数组。其次，随着公式运算，最终只有两种结果，那么就是快乐数，最终一直为1循环，第二种就是无限循环（但是肯定有一次等于最开始输入的n），所以为了寻找目前的n在之前出现过了没有，只要出现就和1进行比较。

map作为哈希表

其实判断map能不能用只需要记住数组和set的缺点就好：

• 数组的大小是受限制的，而且如果元素很少，而哈希值太大会造成内存空间的浪费。
• set是一个集合，里面放的元素只能是一个key，而两数之和这道题目，不仅要判断y是否存在而且还要记录y的下标位置，因为要返回x 和 y的下标。所以set 也不能用。

两数之和

这道题当我们遍历数组的时候，我们需要把现在的nums[i]加进HashMap中，同时，为了一次遍历输出答案，我们还要找target-nums[i]的值目前在HashMap中存在不，如果存在就直接return

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //新建一个哈希表
        Map<Integer,Integer> cnt=new HashMap<>();
        for(int i=0;i<nums.length;i++)
        {
            if(cnt.containsKey(target-nums[i]))
            {
                return new int[]{i,cnt.get(target-nums[i])};
            }
            else
            {
                cnt.put(nums[i],i);
            }
        }
        return new int[0];
        
    }
}

四数相加2

这道题让我想起链表中的环形链表2，我们最后需要借助数学公式来找到等式关系从而进行代码的表达，这道题其实也就是等于numsi+numsj=-（numsk+numsl）。

如果我们用Map和两次循环记录下numsi和numsj的所有值，然后我们遍历两次数组，在我们目前HashMap记录的key中找到-（numsk+numsl），然后将结果加上value就可以了。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        //a+b+c+d=0--a+b=-(c+d)
        Map<Integer,Integer> cnt=new HashMap<>();
        int ans=0;
        for(int i:nums1)
        {
            for(int j:nums2)
            {
                int sum=i+j;
                cnt.put(sum,cnt.getOrDefault(sum,0)+1);
            }
        }
        for(int i:nums3)
        {
            for(int j:nums4)
            {
                int sum=0-i-j;
                if(cnt.containsKey(sum))
                {
                    ans+=cnt.get(sum);
                }
            }
        }
        
        return ans;
    }
}

哈希表不一定有双指针好 

 三数之和

像这种题需要考虑三个元素不能重复的情况，哈希表Map很难处理好所有的情况，建议用双指针。先用i遍历nums【i】第一个元素，然后用left指向i+1，用right指向数组最后一个元素，进行遍历，难点在于去重。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        //数组排序 双指针 去重
        List<List<Integer>> ans=new ArrayList<>();
        Arrays.sort(nums);

        for(int i=0;i<nums.length;i++)
        {
            if(nums[i]>0)
            {
                return ans;
                //顺序来看是num[i] nums[left] nums[right]

            }
            if (i > 0 && nums[i] == nums[i - 1]) {  // 去重a
                continue;
            }


            int left=i+1;
            int right=nums.length-1;
            while(left<right)
            {
                if(nums[i]+nums[left]+nums[right]>0)
                {
                    right--;
                }
                else if(nums[i]+nums[left]+nums[right]<0)
                {
                    left++;
                }
                else{
                    ans.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重逻辑应该放在找到一个三元组之后，对b 和 c去重
                    while (right > left && nums[right] == nums[right - 1]) right--;
                    while (right > left && nums[left] == nums[left + 1]) left++;
                    
                    right--; 
                    left++;
                }

            }
        }
        return ans;
        
    }
}