代码随想录算法训练营第七天 | 454. 四数相加 II、383. 赎金信

454. 四数相加 II

leetcode
文档讲解
视频讲解

很显然，暴力解法的时间复杂度是 n^4。

class Solution {
    public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0, n = nums1.length;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int sum = nums1[i] + nums2[j];
                map.put(sum, map.getOrDefault(sum, 0) + 1);
            }
        }

        for (int k = 0; k < n; k++) {
            for (int l = 0; l < n; l++) {
                int sum = nums3[k] + nums4[l];
                if (map.containsKey(0 - sum)) {
                    count += map.get(0 - sum);
                }
            }
        }

        return count;
    }
}

383. 赎金信

leetcode
文档题解

class Solution {
    public boolean canConstruct(String ransomNote, String magazine) {
        int[] records = new int[26];

        // 统计 ransomNote 中个字符的数量
        for (int i = 0; i < ransomNote.length(); i++) {
            char c = ransomNote.charAt(i);
            records[c - 'a']++;
        }

        // 遍历 magazine，削减 records 相同字符的数量
        for (int i = 0; i < magazine.length(); i++) {
            int c = magazine.charAt(i);
            records[c - 'a']--;
        }

        // 检查 records，如果有字符的数量大于 0，说明 magazine 中的字符还不够，不能构成 ransomNote
        for (int num: records) {
            if (num > 0) return false;
        }

        return true;
    }
}

15. 三数之和

leetcode
文档题解
视频题解