四数相加
程序员文章站
2022-06-28 08:21:14
Leetcode 11.27打个卡(https://github.com/ydSerendipity/Leetcode/blob/master/code/fourNumSumZero.java)给定四个包含整数的数组列表A , B , C , D ,计算有多少个元组 (i, j, k, l),使得A[i] + B[j] + C[k] + D[l] = 0。为了使问题简单化,所有的 A, B, C, D 具有相同的长度N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 ......
Leetcode 11.27打个卡(https://github.com/ydSerendipity/Leetcode/blob/master/code/fourNumSumZero.java)
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ,使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化,所有的 A, B, C, D 具有相同的长度 N,且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间,最终结果不会超过 231 - 1 。(来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/4sum-ii)
拿着题目第一想法直接四个for循环,然后判断,最后返回计数的就可以了,果不其然爆了,就知道没这么简单让我过。没有大佬们那么熟悉直接用哈希,第二次上的是ArrayList,最后还是有个套了3个for循环,提交还是爆了。看了提示说要用哈希,然后恶补了一下哈希:(使用getOrDefault(key, default)时间和空间消耗都要少)
package Leetcode;
import java.util.ArrayList;
import java.util.HashMap;
public class fourNumSumZero {
public static void main(String[] args){
fourNumSumZero obj = new fourNumSumZero();
int[] A = {-1, -1};
int[] B = {-1, 1};
int[] C = {-1, 1};
int[] D = {1, -1};
System.out.println(obj.fourSumCount(A, B, C, D));
}
public int fourSumCount(int[] A, int[] B, int[] C, int[] D){
int len = A.length;
int count = 0;
// ArrayList<Integer> l = new ArrayList<Integer>();
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0;i < len;i++){
for (int j = 0;j < len;j++){
int sum = A[i]+B[j];
// if(map.containsKey(sum)){
// map.put(sum, map.get(sum)+1);
// }else {
// map.put(sum, 1);
// }
// getOrDefault(key, default)是查询有这个key则返回相应的value,没有则返回default值
// 最开始没有,返回default为0,最后加一,这个过程就是在计数的过程
map.put(sum, map.getOrDefault(sum, 0)+1);
}
}
for (int k = 0;k < len;k++){
for (int l = 0;l < len;l++){
int r = C[k] + D[l];
if(map.containsKey(-r)){
count += map.get(-r);
}
}
}
return count;
}
}
本文地址:https://blog.csdn.net/ydydyd00/article/details/110232392
下一篇: MybatisPlus入门学习