哈希表实战：四数相加、赎金信与三/四数之和解法

赎金信

问题描述 判断 ransomNote 能否由 magazine 中的字符构成。magazine 中的字符只能使用一次。

思路解析 本质是字符频次比对。由于只涉及小写字母，使用长度为 26 的整型数组比 HashMap 更高效。下标对应字母偏移量，值存储剩余可用次数。

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        int[] array = new int[26];
        // 统计 magazine 中各字符出现次数
        for (char c : magazine.toCharArray()) {
            array[c - 'a']++;
        }
        // 消耗 ransomNote 中的字符
        for (char d : ransomNote.toCharArray()) {
            array[d - 'a']--;
        }
        // 检查是否有字符不足
        for (int count : array) {
            if (count < 0) {
                return false;
            }
        }
        return true;
    }
}

三数之和

问题描述 找出数组中和为 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++) {
            // 剪枝：如果当前数大于 0，后续不可能和为 0
            if (nums[i] > 0) {
                return result;
            }
            // 去重：跳过重复的第一个元素
            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) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    result.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    // 去重：跳过重复的 b 和 c
                    while (left < right && nums[right] == nums[right - 1]) {
                        right--;
                    }
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++;
                    }
                    right--;
                    left++;
                }
            }
        }
        return result;
    }
}

避坑指南

1. a 的去重判断 nums[i] == nums[i-1] 必须在 i > 0 之后。
2. b 和 c 的去重逻辑必须放在找到一个有效三元组之后，且移动指针前执行。
3. 找到一组解后，记得同时移动左右指针 right-- 和 left++，否则死循环。

四数之和

问题描述 找出数组中和为 target 的不重复四元组。

思路解析 在三数之和基础上增加一层循环。主要区别在于剪枝条件更复杂，因为 target 不固定为 0。

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++) {
            // 剪枝：注意负数情况，不能简单判断 nums[i] > target
            if (nums[i] > target && nums[i] >= 0) {
                break;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            
            for (int j = i + 1; j < nums.length; j++) {
                // 第二个元素的剪枝
                if (nums[i] + nums[j] > target && nums[i] + nums[j] >= 0) {
                    break;
                }
                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 > target) {
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        result.add(Arrays.asList(nums[i], nums[j], nums[left], nums[right]));
                        while (left < right && nums[right] == nums[right - 1]) {
                            right--;
                        }
                        while (left < right && nums[left] == nums[left + 1]) {
                            left++;
                        }
                        right--;
                        left++;
                    }
                }
            }
        }
        return result;
    }
}

技术总结 哈希表选型建议：

1. Map: 当需要记录数值及其下标（如两数之和返回索引）时使用。空间开销较大，维护红黑树或符号表有成本。
2. 数组: 当哈希值范围有限且连续（如字符映射 0-255）时，数组效率最高，无哈希冲突开销。
3. Set: 仅用于判断存在性，无法记录额外信息（如下标）。若需返回下标则不适用。

实际开发中，根据数据特征（稀疏度、范围、是否需关联值）灵活选择，避免过度设计。