哈希表

1.理论基础

哈希表是根据关键码的值直接进行访问的数据结构。（数组其实就是一个简单的哈希表

一般哈希表都是用来快速判断一个元素是否出现在集合里的。

常见的三种哈希结构：

数组
set（集合）
map（映射）

2. 有效的字母异位词

题目：给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。说明：你可以假设字符串只包含小写字母。

题目分析：定义一个record数组存放26个字母，遍历s的字符+1，遍历t的字符-1，看最后record的值是否全为0，是则返回true，否则返回false。

class Solution {
    public boolean isAnagram(String s, String t) {
        int[] record = new int[26];
        for(char c : s.toCharArray()){
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[c - 'a'] += 1;
        }
        for(char c : t.toCharArray()){
            record[c - 'a'] -= 1;
        }

        for(int i : record){
            if(i != 0){
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
            }
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }
}

3. 两个数组的交集

题目：给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是唯一的。我们可以 不考虑输出结果的顺序 。

题目分析：输出的结果要去重。

import java.util.HashSet;
import java.util.Set;

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums2 == null || nums1.length == 0 || nums2.length == 0){
            return new int[0];
        }
        Set<Integer> set = new HashSet<>();
        Set<Integer> resSet = new HashSet<>();
        //遍历nums1
        for(int i : nums1){
            set.add(i);
        }
        //遍历nums2的过程中判断哈希表中是否存在该元素
        for(int i : nums2){
            if(set.contains(i)){
                resSet.add(i);
            }
        }
        int[] resArr = new int[resSet.size()];
        int index = 0;
        //将结果转换成数组
        for(int i : resSet){
            resArr[index++] = i;
        }
        return resArr;
    }
}

4. 快乐数

题目：编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果可以变为 1，那么这个数就是快乐数。如果 n 是快乐数就返回 True ；不是，则返回 False 。

题目分析：求和的过程中，sum会重复出现。使用哈希法来判断sum是否重复出现，重复了就false，否则一直找到1为止。

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> record = new HashSet<>();
        // 如果这个sum曾经出现过，说明已经陷入了无限循环了
        while(n != 1 && !record.contains(n)){
            record.add(n);
            n = getNextNumber(n);
        }
        return n == 1;
    }
    public int getNextNumber(int n){
        int res = 0;
        while(n > 0){
            int temp = n % 10; //求最后一位数
            res += temp * temp;
            n /= 10; //缩小n
        }
        return res;
    }
}

5. 两数之和

题目：给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

class Solution {
    //数组两层for循环也可
    public int[] twoSum(int[] nums, int target) {
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                if(target == nums[i] + nums[j]){
                    return new int[]{i, j};
                }
            }
        }
        return new int[0];
    }
    
    //Map也可
    public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if(nums == null || nums.length == 0){
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>();
    for(int i = 0; i < nums.length; i++){
        int temp = target - nums[i];
        if(map.containsKey(temp)){
            res[1] = i;
            res[0] = map.get(temp);
        }
        map.put(nums[i], i);
    }
    return res;
}
}

6. 四数相加II

题目：给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

题目分析：**使用哈希法的经典题目。**这道题目是四个独立的数组，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考虑有重复的四个元素相加等于0的情况

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int temp;
        int res = 0;
        //统计两个数组中的元素之和，同时统计出现的次数，放入map
        for (int i : nums1) {
            for (int j : nums2) {
                temp = i + j;
                if (map.containsKey(temp)) {
                    map.put(temp, map.get(temp) + 1);
                } else {
                    map.put(temp, 1);
                }
            }
        }
        //统计剩余的两个元素的和，在map中找是否存在相加为0的情况，同时记录次数
        for (int i : nums3) {
            for (int j : nums4) {
                temp = i + j;
                if (map.containsKey(0 - temp)) {
                    res += map.get(0 - temp);
                }
            }
        }
        return res;
    }
}

7. 赎金信

题目：给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。(题目说明：为了不暴露赎金信字迹，要从杂志上搜索各个需要的字母，组成单词来表达意思。杂志字符串中的每个字符只能在赎金信字符串中使用一次。)你可以假设两个字符串均只含有小写字母。

题目分析：杂志里面的字母不可重复使用。只有小写字母。因为题目只有小写字母，就可以用一个长度为26的数组去记录magazine里字母出现的次数，再用该数组去验证ransomNote是否包含了这些字母。(要求只有小写字母，就用数组)

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        //记录杂志字符串出现的次数
        int[] arr = new int[26];
        int temp;
        for (int i = 0; i < magazine.length(); i++) {
            temp = magazine.charAt(i) - 'a';
            arr[temp]++;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            temp = ransomNote.charAt(i) - 'a';
            //对于金信中的每一个字符都在数组中查找
            //找到相应位减一，否则找不到返回false
            if (arr[temp] > 0) {
                arr[temp]--;
            } else {
                return false;
            }
        }
        return true;
    }
}

8. 三数之和

题目：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意： 答案中不可以包含重复的三元组。

题目分析：用哈希法并不合适，在去重的操作上难免会出现查错。

**用双指针方法更高效一些：**先将数组进行排序，i从下标0开始，left在i + 1 的位置，right在数组结尾处。指针进行移动，如果三者数之和大了，right就要向左移动；三者数小了就要left向右移动，直到left和right相遇。

双指针解法是一层for循环num[i]为确定值，然后循环内有left和right下标作为双指针，找到nums[i] + nums[left] + nums[right] == 0。（就是拿两个值来双指针，其他作为确定值，以后五位数、六位数等等之和，一样的方法

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);

        for (int i = 0; i < nums.length; i++) {
            // 排序之后如果第一个元素已经大于零，那么无论如何组合都不可能凑成三元组，直接返回结果就可以了
            if (nums[i] > 0) {
                return result;
            }

            // 正确去重方法：就是以nums[i]作为确定值，在后面去找符合条件的数。如果下一个元素跟上个元素一样就不用继续了，直接跳过。
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1;
            int right = nums.length - 1;
            while (right > left) {
                // 去重复逻辑如果放在这里，0，0，0 的情况，可能直接导致 right<=left 了，从而漏掉了 0,0,0 这种三元组
                /*
                while (right > left && nums[right] == nums[right - 1]) right--;
                while (right > left && nums[left] == nums[left + 1]) left++;
                */
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));

                    // 去重逻辑应该放在找到一个三元组之后
                    while (right > left && nums[right] == nums[right - 1]){
                        right--;
                    } 
                    while (right > left && nums[left] == nums[left + 1]){
                        left++;
                    }
                    
                     // 找到答案时，双指针同时收缩
                    right--; 
                    left++;
                }
            }
        }
        return result;
    }
}

9. 四数之和

题目：给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。**注意：**答案中不可以包含重复的四元组。

题目分析;双指针解法是两层for循环nums[k] + nums[i]为确定值，依然是循环内有left和right下标作为双指针，找出nums[k] + nums[i] + nums[left] + nums[right] == target的情况.

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(nums);
       
        for (int i = 0; i < nums.length; i++) {

             // 去重
            if (i > 0 && nums[i - 1] == nums[i]) {
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {
                // 正确去重方法
                if (j > i + 1 && nums[j - 1] == nums[j]) {
                    continue;
                }

                int left = j + 1;
                int right = nums.length - 1;
                while (right > left) {
                    int sum = nums[i] + nums[j] + nums[left] + nums[right];
                    if (sum > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        // 去重逻辑应该放在找到一个四元组之后
                        while (right > left && nums[right] == nums[right - 1]) right--;
                        while (right > left && nums[left] == nums[left + 1]) left++;

                        // 找到答案时，双指针同时收缩
                        left++;
                        right--;
                    }
                }
            }
        }
        return result;
    }
}