题目:给你四个整数数组 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)链接
题解:
- 自己做的方法,四层for循环,复杂度太高,超出时间限制
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { int n = nums1.length; int count = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { for (int k = 0; k < n; k++) { for (int l = 0; l < n; l++) { if (nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0) { count++; } } } } } return count; } }
- 利用map,降低复杂度
class Solution { public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) { //map存放num1和nums2中两个元素的和和对应的个数 Map<Integer, Integer> map = new HashMap<>(); int temp = 0; int count = 0; for (int i : nums1) { for (int j : nums2) { temp = i + j; if (map.containsKey(temp)) { map.put(temp, map.get(temp) + 1); } else { map.put(temp, 1); } } } //循环遍历nums3和nums4,并在map中查找0-(k+l),匹配成功说明4数之和为0 for (int k : nums3) { for (int l : nums4) { temp = k + l; if (map.containsKey(0 - temp)) { count += map.get(0 - temp); } } } return count; } }