自己做网站吗,淘宝运营自学教程入门,谷歌搜索引擎网页版入口,网络营销推广服务合同文章目录 需求代码结尾 需求
给你四个整数数组 nums1、nums2、nums3 和 nums4 #xff0c;数组长度都是 n #xff0c;请你计算有多少个元组 (i, j, k, l) 能满足#xff1a; 0 i, j, k, l n nums1[i] nums2[j] nums3[k] nums4[l] 0 示例 1#xff1a; 输入… 文章目录 需求代码结尾 需求
给你四个整数数组 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 解释 两个元组如下 (0, 0, 0, 1) - nums1[0] nums2[0] nums3[0] nums4[1] 1 (-2) (-1) 2 0(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 -228 nums1[i], nums2[i], nums3[i], nums4[i] 228 代码
思路挺简单的, 就是遍历前两个数组, 将其能加起来的和的情况保存在map里, key是和, value是出现的次数, 然后再维护一个count来记录返回值, 再遍历后两个数组, 将其相加的和的负数去map里找, 有的话将 count 加上其value.
代码:
public int fourSumCount(int[] nums1, int[] nums2, int[] nums3, int[] nums4) {int length nums1.length;MapInteger, Integer map new HashMap(length * length);for (int i 0; i length; i) {for (int j 0; j length; j) {int n nums1[i] nums2[j];map.put(n, map.getOrDefault(n, 0) 1);}}int count 0;for (int i 0; i length; i) {for (int j 0; j length; j) {int n nums3[i] nums4[j];if( map.containsKey(-n) ){count map.get(-n);}}}return count;
}代码解释 初始化:
int length nums1.length;
MapInteger, Integer map new HashMap(length * length);获取数组的长度假设所有数组长度相等。 创建一个 HashMap 用于存储 nums1 和 nums2 元素之和的出现频次。length * length 是一个初始容量估计理论上足够容纳所有可能的和。 填充 HashMap:
for (int i 0; i length; i) {for (int j 0; j length; j) {int n nums1[i] nums2[j];map.put(n, map.getOrDefault(n, 0) 1);}
}使用两层嵌套循环遍历 nums1 和 nums2 的所有组合计算它们的和并将和及其出现的次数存入 map 中。 计算四元组数量:
int count 0;
for (int i 0; i length; i) {for (int j 0; j length; j) {int n nums3[i] nums4[j];if (map.containsKey(-n)) {count map.get(-n);}}
}通过两层嵌套循环遍历 nums3 和 nums4 的所有组合计算它们的和。 对于每个和 n检查 map 是否包含 -n。如果包含则将 map 中 -n 的计数值加到 count 中。 为什么是 -n因为我们需要找到 a b c d 0 的情况即 a b - (c d)。所以对于 c d 的和我们需要在 map 中查找与之相反的值。 返回结果: return count; 返回符合条件的四元组的数量。 执行结果: 结尾
以上 是我对这道算法的一些遐想和延伸, 可能不是最优解, 但是算法的优化嘛 本身就是一个思索的过程, 能在这个思索和迭代的过程中有所收获和乐趣就是在成长了, 欢迎大家一起来交流更多的解答…
