Day7 哈希表 part2

2025-06-05

java

四数相加

四数相加 II

HashMap 存一个数组，如 A。然后计算三个数组之和，如 BCD。时间复杂度为：O(n)+O(n^3)，得到 O(n^3).

HashMap 存三个数组之和，如 ABC。然后计算一个数组，如 D。时间复杂度为：O(n^3)+O(n)，得到 O(n^3).

HashMap存两个数组之和，如AB。然后计算两个数组之和，如 CD。时间复杂度为：O(n^2)+O(n^2)，得到 O(n^2).

我们以存 AB 两数组之和为例。首先求出 A 和 B 任意两数之和 sumAB，以 sumAB 为 key，sumAB 出现的次数为 value，存入 hashmap 中。

然后计算 C 和 D 中任意两数之和的相反数 sumCD，在 hashmap 中查找是否存在 key 为 sumCD。

    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        HashMap<Integer, Integer> result = new HashMap<>();
        int count = 0;
        for (int i = 0; i < nums1.length; i++) {
            for (int j = 0; j < nums2.length; j++) {
                int sumAB = nums1[i] + nums2[j];
                if (result.containsKey(sumAB)) {
                    result.put(sumAB, result.get(sumAB) + 1);
                } else {
                    result.put(sumAB, 1);
                }
            }
        }

        for (int i = 0; i < nums3.length; i++) {
            for (int j = 0; j < nums4.length; j++) {
                int sumCD = nums3[i] + nums4[j];
                if (result.containsKey(-sumCD)) {
                    count += result.get(-sumCD);
                }
            }
        }
        return count;
    }

赎金信

赎金信

用一个长度为26的数组来记录magazine里字母出现的次数。

然后再用ransomNote 去验证这个数组是否包含了ransomNote 所需要的所有字母。

千万注意，magazine肯定是更长的，并且类似于字典，我们是统计他字母出现次数，后面需要的才能从里面减少

    public boolean canConstruct(String ransomNote, String magazine) {
        //题意条件 1 <= ransomNote.length, magazine.length <= 105
        if (ransomNote.length() > magazine.length()) {
            return false;
        }
        //不用map，因为空间开销大，用数组，储存a~z
        int[] record = new int[26];
        //遍历，统计字母出现次数
        for (int i = 0; i < magazine.length(); i++) {
            int index = magazine.charAt(i) - 'a';
            record[index] += 1;
        }
        for (int i = 0; i < ransomNote.length(); i++) {
            int index = ransomNote.charAt(i) - 'a';
            record[index] -= 1;
        }
        // 如果数组中存在负数，说明ransomNote字符串中存在magazine中没有的字符
        for (int i : record) {
            if (i < 0) {
                return false;
            }
        }
        return true;
    }