Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[i] + B[j] + C[k] + D[l]is zero.
To make problem a bit easier, all A, B, C, D have same length of N where 0 ≤ N ≤ 500. All integers are in the range of -228 to 228 - 1 and the result is guaranteed to be at most 231 - 1.
Example:
Input: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2 Explanation: The two tuples are: 1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0 2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0 import java.util.HashMap; import java.util.Map; public class Main { //和作为key，种数作为value //先循环遍历两个数组，把对应下标的两个元素的和作为key存储到map中， // 如果map中暂无该key，则对应的value为1（因为目前为止组合为该和的种数是1） //如果map中已经有该key，说明这是第二种或第n种为该和的组合,则对应的value加1 public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < C.length; i++) { for (int j = 0; j < D.length; j++) { int sum = C[i] + D[j]; map.put(sum, map.getOrDefault(sum, 0) + 1); } } //当A B 中存在符合条件的组合时，会把C D 中为该和的组合种数加到res中，则最后的res表示结果数 int res = 0; for (int i = 0; i < A.length; i++) { for (int j = 0; j < B.length; j++) { res += map.getOrDefault(-1 * (A[i] + B[j]), 0);//b*(-1) =a ,则 a+b = 0 } } return res; } /** * 报错 Time Limit Exceeded * * @param A * @param B * @param C * @param D * @return */ public int fourSumCount2(int[] A, int[] B, int[] C, int[] D) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < A.length; i++) { for (int j = 0; j < B.length; j++) { for (int k = 0; k < C.length; k++) { int sum = A[i] + B[j] + C[k]; map.put(sum, map.getOrDefault(sum, 0) + 1);//每次put都要加1 } } } int res = 0; for (int i = 0; i < D.length; i++) { res += map.getOrDefault(-1 * D[i], 0); } return res; } /** * Runtime: 74 ms, faster than 21.91% of Java online submissions for 4Sum II. * Memory Usage: 58 MB, less than 76.62% of Java online submissions for 4Sum II. * * @param A * @param B * @param C * @param D * @return */ public int fourSumCount3(int[] A, int[] B, int[] C, int[] D) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < A.length; i++) { for (int j = 0; j < B.length; j++) { int sum = A[i] + B[j]; map.put(sum, map.getOrDefault(sum, 0) + 1);//每次put都要加1 } } int res = 0; for (int k = 0; k < C.length; k++) { for (int l = 0; l < D.length; l++) { res += map.getOrDefault(-1 * (C[k] + D[l]), 0); } } return res; } public static void main(String[] args) { int[] A = new int[]{1, 2, 2}; int[] B = new int[]{-2, -1, 2}; int[] C = new int[]{-1, 2, -2}; int[] D = new int[]{0, 2, -2}; Main main = new Main(); System.out.println(main.fourSumCount(A, B, C, D));//12 } }48 / 48 test cases passed. Status: Accepted Runtime: 170 ms Your runtime beats 76.40 % of java submissions. T(n) = O(n^2)
