leetcode 哈希表篇

哈希表的一些概念

HashMap 和 HashSet 都是 Java 集合框架的重要组件，它们的主要区别在于以下几个方面：

1.存储方式不同：HashMap 存储的是键值对，将键映射到值，可通过键来访问值；而 HashSet 存储的是唯一值的集合。

2.实现方式不同：HashMap 内部采用的是哈希表数据结构来存储键值对，而 HashSet 采用的是哈希表或者二叉树数据结构来存储唯一值的集合。

3.数据访问方式不同：HashMap 可以通过键来访问对应的值，通过 get() 方法实现；而 HashSet 只能通过迭代器或者 forEach() 方法来遍历元素，没有直接获取单个元素的方法。

4.存储特点不同：HashSet 存储的是唯一的元素集合，不允许存在重复的元素；而 HashMap 存储的是键值对，键是唯一的，而值可以重复。

5.扩容方式不同：HashMap 扩容的时候会重新调整内部存储结构，将所有键值对重新散列到新的存储区域中；而 HashSet 扩容则仅仅只是增加了哈希桶的数量，然后将原有的元素重新分配到新的桶中。

关于HashMap的其他常用方法

put(K key, V value): 将指定的值与此映射中的指定键关联（可选操作）。
get(Object key): 返回到指定键所映射的值，或 null（如果此映射包含该键的映射关系）。
remove(Object key): 如果存在一个键的映射关系，则将其从此映射中移除（可选操作）。
containsKey(Object key): 如果此映射包含指定键的映射关系，则返回 true。
keySet(): 返回此映射中包含的键的 Set 视图。
values(): 返回此映射中包含的值的 Collection 视图。

一、有效的字母异位词

力扣题目链接

给定两个字符串 *s* 和 *t* ，编写一个函数来判断 *t* 是否是 *s* 的字母异位词。

注意：若 *s* 和 *t* 中每个字符出现的次数都相同，则称 *s* 和 *t* 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

• 1 <= s.length, t.length <= 5 * 104
• s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()){
            return false; 
        }
        Map<Character,Integer> table = new HashMap<Character,Integer>();
        for (int i=0 ;i<s.length();i++){
            char ch = s.charAt(i);
            table.put(ch,table.getOrDefault(ch,0)+1);
        }
        for (int i=0 ;i<t.length();i++){
            char ch = t.charAt(i);
            table.put(ch,table.getOrDefault(ch,0)-1);
            if(table.get(ch)<0){
                return false;
            }
        }
        return true;
        
    }
}

二、两个数组的交集

力扣题目链接

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

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]

示例 2：

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的

提示：

• 1 <= nums1.length, nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 1000

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

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        if(nums1 == null || nums1.length==0 || nums2==null || nums2.length==0 ){
            return new int[0];
        }
        Set<Integer> set1 = new HashSet<Integer>();
        Set<Integer> set2 = new HashSet<Integer>();
        for (int i : nums1){
            set1.add(i);
        }
        for(int i : nums2){
            if(set1.contains(i)){
                set2.add(i);
            }
        }
        int[] result = new int [set2.size()];
        int j = 0;
        for (int i : set2){
            result[j++] = i;
        }
        return result;
    }
}

注意学习HashSet的用法，在 Java 中，HashSet 是基于 HashMap 实现的，它不允许存储重复的元素。如果尝试向 HashSet 中添加一个已经存在的元素，这个添加操作将会失败，但不会引发任何异常。HashSet 的 add 方法在添加成功时返回 true，如果元素已经存在，则返回 false。

在上述代码中，HashSet 被用于存储 nums1 和 nums2 数组中的元素。由于 HashSet 不存储重复的元素，所以即使 nums1 或 nums2 中包含重复的值，这些值在 HashSet 中只会存储一次。这样，当检查 nums2 中的元素是否存在于 nums1 对应的 HashSet（set1）中时，即使 nums2 中有重复的元素，结果集 resSet 也只会包含不重复的交集元素。

此外，提供另外一种输出方式

return set2.stream().mapToInt(x -> x).toArray();

是Java 8中的一行代码，它使用了Java的Stream API和Lambda表达式。这行代码的功能是将一个Integer类型的集合（如Set<Integer>）转换为一个整型数组。下面是这行代码的详细解释：

• set2.stream()：这会将set2（一个集合）转换为一个流（Stream）。流是Java 8中引入的一个新概念，它允许你以声明性方式处理数据。
• .mapToInt(x -> x)：这是一个中间操作，它会将流中的每个元素转换为一个int。x -> x是一个Lambda表达式，表示对流中的每个元素执行的操作。在这里，它实际上是一个恒等函数，因为它返回的值与输入的值相同。
• .toArray()：这是一个终端操作，它会收集流中的所有元素，并将它们放入一个数组中。

所以，这行代码的总体效果是将set2中的所有元素收集到一个整型数组中，并返回这个数组。

三、快乐数

力扣题目链接

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

示例 1：

输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

示例 2：

输入：n = 2
输出：false

提示：

• 1 <= n <= 2^31 - 1

class Solution {
    public boolean isHappy(int n) {
        Set<Integer> set1 = new HashSet<Integer>();
        while(n!=1 && !set1.contains(n)){
            set1.add(n);
            n = getNextNum(n);            
        }
        if(n==1){
            return true;
        }else{
            return false;
        }

    }
    public int getNextNum(int n){
        int result=0;
        while(n!=0){
            int num = n%10;
            result += num * num;
            n = n/10;
        }
        return result;
    }
}

四、两数之和

力扣题目链接

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

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

五、四数相加2

力扣题目链接

给你四个整数数组 nums1、nums2、nums3 和 nums4 ，数组长度都是 n ，请你计算有多少个元组 (i, j, k, l) 能满足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

示例 1：

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2
解释：
两个元组如下：
1. (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
2. (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0

示例 2：

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

提示：

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -228 <= nums1[i], nums2[i], nums3[i], nums4[i] <= 228

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer,Integer> map1 = new HashMap<>();
        int result = 0;
        for (int i = 0; i < nums1.length ; i++){
            for (int j = 0; j < nums2.length ;j++){
                int sum = nums1[i] + nums2[j];
                map1.put(sum,map1.getOrDefault(sum,0)+1);
            }
        }
        for (int i = 0; i < nums3.length; i++){
            for (int j = 0;j < nums4.length; j++){
                int sum = 0 - (nums3[i] + nums4[j]);
                if (map1.containsKey(sum)){
                    result += map1.get(sum);
                }
            }
        }
        return result;

    }
}

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

六、赎金信

力扣题目链接

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。

如果可以，返回 true ；否则返回 false 。

magazine 中的每个字符只能在 ransomNote 中使用一次。

示例 1：

输入：ransomNote = "a", magazine = "b"
输出：false

示例 2：

输入：ransomNote = "aa", magazine = "ab"
输出：false

示例 3：

输入：ransomNote = "aa", magazine = "aab"
输出：true

提示：

• 1 <= ransomNote.length, magazine.length <= 105
• ransomNote 和 magazine 由小写英文字母组成

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        Map<Character,Integer> map = new HashMap<>();
        
        for (char ch : magazine.toCharArray()){
            map.put(ch , map.getOrDefault(ch,0) + 1);
        }
        for (char ch : ransomNote.toCharArray()){
            if (map.containsKey(ch)){
                map.put(ch , map.get(ch)-1);
                if(map.get(ch) < 0){
                    return false;
                }
            }else{
                return false;
            }
        }
        return true;
    }
}

补充一些字符串的用法：

在Java中，遍历字符串通常指的是按顺序访问字符串中的每个字符。由于字符串在Java中被表示为String对象，可以通过几种不同的方式来遍历它们：

1. 使用传统的for循环：

这是最基本的方法，使用字符串的长度和charAt方法来访问每个字符。

javaCopy codeString str = "Hello, World!";
for (int i = 0; i < str.length(); i++) {
    char ch = str.charAt(i);
    // 处理ch
}

2. 使用for-each循环和toCharArray方法：

首先将字符串转换为字符数组，然后使用for-each循环遍历这个数组。

javaCopy codeString str = "Hello, World!";
for (char ch : str.toCharArray()) {
    // 处理ch
}

3. 使用Java 8的chars方法：

Java 8引入了chars方法，它返回一个IntStream，这是字符的数值表示形式的流。然后可以使用lambda表达式处理每个字符。

javaCopy codeString str = "Hello, World!";
str.chars().forEach(c -> {
    char ch = (char) c;
    // 处理ch
});

4. 使用Java 8的codePoints方法：

对于需要处理Unicode代理对（即代码点大于U+FFFF的字符）的情况，codePoints方法会更加合适。它返回一个代表字符串中所有代码点的流。

javaCopy codeString str = "Hello, World!";
str.codePoints().forEach(cp -> {
    char[] chars = Character.toChars(cp);
    // 处理chars
});

在大多数情况下，前两种方法已经足够使用。但是，如果您处理的字符串包含Unicode代理对，或者您想利用流的特性（如并行处理），那么使用chars或codePoints方法可能更合适。

七、三数之和

力扣题目链接

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请

你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

示例 1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
解释：
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意，输出的顺序和三元组的顺序并不重要。

示例 2：

输入：nums = [0,1,1]
输出：[]
解释：唯一可能的三元组和不为 0 。

示例 3：

输入：nums = [0,0,0]
输出：[[0,0,0]]
解释：唯一可能的三元组和为 0 。

提示：

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

// 使用双指针法
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        for (int i=0 ;i<nums.length-2;i++){
            // 确保在数组中遇到一个与前一个元素相同的元素时，会跳过它，从而避免了重复的三元组。
            if (i>0 && nums[i]==nums[i-1]){
                continue;
            }
            int left = i+1;
            int right = nums.length-1;
            while(left < right){
                int sum = nums[i] + nums[left] + nums[right];
                if(sum == 0){
                    result.add(Arrays.asList(nums[i],nums[left],nums[right]));
                    while(left<right&&nums[left]==nums[left+1]){
                        left++;
                    }
                    while(left<right&&nums[right]==nums[right-1]){
                        right--;
                    }
                    left++;
                    right--;
                }else if (sum<0){
                    left++;
                }else{
                    right--;
                }
            }     
        }
        return result;

    }
}

八、四数之和

力扣题目链接

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案 。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [2,2,2,2,2], target = 8
输出：[[2,2,2,2]]

提示：

• 1 <= nums.length <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Long targetNew = (long) target;
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        if (nums.length<4){
            return result;
        }
        for(int i = 0; i < nums.length-3; i++){
            if (i>0 &&nums[i]==nums[i-1]){
                continue;
            }
            for(int j = i+1 ;j < nums.length-2; j++){
                if((j>i+1)&&(nums[j]==nums[j-1])){
                    continue;
                }
                int left = j+1;
                int right = nums.length-1;
                while(left<right){
                    long sum = (long) nums[i] + nums[j] + nums[left] + nums[right];
                    if(sum == targetNew){
                        result.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));
                        while(left < right && nums[left] == nums[left+1]){
                            left++;
                        }
                        while(left < right && nums[right] == nums[right-1]){
                            right--;
                        }
                        left++;
                        right--;
                    }else if(sum < targetNew){
                        left++;
                    }else{
                        right--;
                    }
                }
            }

        }
        return result;
    }
}

其中，有个注意事项是sum超出了 int的最大范围，导致有两个用例没有通过，所以需要进行强制转化。

在Java中，int 类型是一个 32 位的有符号整数类型。其取值范围是从 -2^31 到 2^31 - 1，具体来说：

• 最小值是 -2,147,483,648 （即 -2^31）。
• 最大值是 2,147,483,647 （即 2^31 - 1）。

这个范围确保了int类型可以存储的任何整数值都在这个范围内。如果需要更大的数值范围，可以考虑使用long类型，它是一个64位的有符号整数类型，其范围远大于int。

题目中的10^9 其实已经做出了提醒。

九、总结篇