Day12——哈希表专题

- 日理万妓 2024-04-03 14:19 77阅读 0赞

#### 文章目录 ####

*   *   *  23.快乐数
         *  24.两数之和
         *  25.四数相加

--------------------

#### 23.快乐数 ####

**通过哈希判重：**

这道题目使用哈希法，来判断这个res是否重复出现，如果重复了就是return false， 否则一直找到sum为1为止，则返回true

class Solution {
        
        public boolean isHappy(int n) {
        
            HashSet<Integer> hashSet = new HashSet<>();
            while (n != 1 && !hashSet.contains(n)) {
        
                hashSet.add(n);
                n = getnextNumber(n);
            }
            return n == 1;
        }
    
            private int getnextNumber(int n){
        
                int res = 0;
                while (n>0){
        
                    int i = n%10;
                    res+=i*i;
                    n = n/10;
                }
                return res;
            }
    }

#### 24.两数之和 ####

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素比配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素。

*  对于每一个x，我们判断哈希表中是否存在target-x，若存在，则返回哈希表里的value和x的value
 *  反之将x的插入哈希表即可

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

#### 25.四数相加 ####

**本题解题步骤：**

1.  首先定义 一个unordered\_map，key放a和b两数之和，value 放a和b两数之和出现的次数。
2.  遍历大A和大B数组，统计两个数组元素之和，和出现的次数，放到map中。
3.  定义int变量count，用来统计 a+b+c+d = 0 出现的次数。
4.  在遍历大C和大D数组，找到如果 0-(c+d) 在map中出现过的话，就用count把map中key对应的value也就是出现次数统计出来。
5.  最后返回统计值 count 就可以了

class Solution {
        
       public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        
            HashMap<Integer, Integer> hashMap = new HashMap<>();
            int temp;
            int res = 0;
            for (int i : nums1) {
        
                for (int j : nums2) {
        
                    temp = i + j;
                    if(hashMap.containsKey(temp)){
        
                        hashMap.put(temp, hashMap.get(temp)+1);
                    }else {
        
                        hashMap.put(temp,1);
                    }
                    
                }
            }
            for (int i : nums3) {
        
                for (int j : nums4) {
        
                    temp = i+j;
                    if(hashMap.containsKey(0-temp)){
        
                        res+= hashMap.get(0-temp);
                    }
                }
            }
            return res;
        }
    }