【LeetCode·中等】454.四数相加 II (4sum-ii)题目描述 英文版描述 Given four inte

题目描述

英文版描述

Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:

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

Example 1:

Input: nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]

Output: 2

Explanation: The two tuples are: 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

Example 2:

Input: nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]

Output: 1

Constraints:

• n == nums1.length
• n == nums2.length
• n == nums3.length
• n == nums4.length
• 1 <= n <= 200
• -2(28) <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2(28)

英文版地址

leetcode.com/problems/4s…

中文版描述

给你四个整数数组 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
• -2(28) <= nums1[i], nums2[i], nums3[i], nums4[i] <= 2(28)

中文版地址

leetcode.cn/problems/4s…

解题方法

俺这版

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

复杂度分析

• 时间复杂度：O(n^2)，n为数组长度
• 空间复杂度：O(n)

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