代码随想录算法笔记哈希表篇

哈希表

有效的字母异位词

• 核心思想：利用数组模拟哈希表，统计字符出现次数。
• 实现步骤：
  1. 定义长度 26 的数组（对应 26 个小写字母）。
  2. 遍历第一个字符串，累加字符计数；遍历第二个字符串，递减计数。
  3. 若数组所有元素为 0，则为异位词。
• 代码示例：

class Solution { 
    public boolean isAnagram(String s, String t) { 
        int[] hash = new int[26]; 
        for(char c : s.toCharArray()) hash[c - 'a']++; 
        for(char c : t.toCharArray()) hash[c - 'a']--; 
        for(int count : hash) if(count != 0) return false; 
        return true;
    }
}

两个数组的交集

• 核心方法：利用 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<>(); 
        Set<Integer> result = new HashSet<>(); 
        for(int num : nums1) set1.add(num); 
        for(int num : nums2) if(set1.contains(num)) result.add(num); 
        // 转换为数组
        int[] arr = new int[result.size()]; 
        int i = 0; 
        for(int num : result) arr[i++] = num; 
        return arr;
    }
}

快乐数

• 核心定义：快乐数是指无限次替换后最终为 1 的数，若进入循环则不是。
• 实现步骤：
  1. 用 Set 检测循环（重复出现的数）。
  2. 编写方法计算每一位平方和。
• 代码示例：

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

两数之和

• 核心思路：利用 HashMap 存储元素值与下标，遍历过程中查找目标差值。
• 代码示例：

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

四数相加 II

• 核心技巧：分组求和，前两组和存入 HashMap，后两组和查找互补值。
• 代码示例：

class Solution { 
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { 
        Map<Integer, Integer> map = new HashMap<>(); 
        int res = 0; 
        // 存储前两组和的计数
        for(int i : nums1) { 
            for(int j : nums2) { 
                int sum = i + j; 
                map.put(sum, map.getOrDefault(sum, 0) + 1); 
            }
        }
        // 查找后两组和的互补值
        for(int i : nums3) { 
            for(int j : nums4) { 
                res += map.getOrDefault(-(i + j), 0); 
            }
        }
        return res;
    }
}

赎金信

• 核心逻辑：同字母异位词，验证杂志字符是否足够组成赎金信。
• 代码示例：

class Solution { 
    public boolean canConstruct(String ransomNote, String magazine) { 
        int[] hash = new int[26]; 
        for(char c : magazine.toCharArray()) hash[c - 'a']++; 
        for(char c : ransomNote.toCharArray()) { 
            hash[c - 'a']--; 
            if(hash[c - 'a'] < 0) return false; 
        }
        return true;
    }
}

三数之和

• 核心方法：排序 + 双指针，避免三重循环，同时处理去重。
• 实现步骤：
  1. 数组排序，固定第一个数 nums[i]。
  2. 双指针 left = i+1、right = n-1，寻找和为 0 的组合。
  3. 去重：nums[i] == nums[i-1] 跳过；找到组合后，left、right 跳过重复值。
• 代码示例：

import java.util.Arrays;
class Solution { 
    public List<List<Integer>> threeSum(int[] nums) { 
        List<List<Integer>> res = new ArrayList<>(); 
        Arrays.sort(nums); 
        for(int i = 0; i < nums.length; i++){ 
            if(nums[i] > 0) return res; // 第一个数大于0，和不可能为0
            // 去重a
            if(i > 0 && nums[i] == nums[i-1]) continue; 
            int left = i + 1; 
            int right = nums.length - 1; 
            while(right > left){ 
                int sum = nums[i] + nums[left] + nums[right]; 
                if(sum > 0) right--; 
                else if(sum < 0) left++; 
                else{ 
                    res.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 res;
    }
}

四数之和

• 核心思路：在三数之和基础上增加一层循环，额外处理去枝和去重。
• 去枝条件：nums[i] > target && target > 0（避免目标为负数时误判）。
• 代码示例：

import java.util.Arrays;
class Solution { 
    public List<List<Integer>> fourSum(int[] nums, int target) { 
        List<List<Integer>> res = new ArrayList<>(); 
        Arrays.sort(nums); 
        int n = nums.length; 
        for(int i = 0; i < n - 3; i++){ 
            // 去枝a
            if(nums[i] > target && target > 0) return res; 
            // 去重a
            if(i > 0 && nums[i] == nums[i-1]) continue; 
            for(int j = i + 1; j < n - 2; j++){ 
                // 去枝b
                if(nums[i] + nums[j] > target && target > 0) return res; 
                // 去重b
                if(j > i + 1 && nums[j] == nums[j-1]) continue; 
                int left = j + 1; 
                int right = n - 1; 
                while(right > left){ 
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right]; // 防溢出
                    if(sum > target) right--; 
                    else if(sum < target) left++; 
                    else{ 
                        res.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right])); 
                        // 去重c和d
                        while(right > left && nums[right] == nums[right-1]) right--; 
                        while(right > left && nums[left] == nums[left+1]) left++; 
                        right--; 
                        left++; 
                    }
                }
            }
        }
        return res;
    }
}