[LeetCode] 454. 4Sum II 四数之和II
LeetCode II 四数
2023-09-27 14:28:37 时间
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
在给定的4个数组中各取1个数字,使4个数的和为0,返回找到的次数。
如果用暴力搜索Bruce Force,那么Time: O(n^4),用时太长。
好的解法是用Hash map,建立一个map,将A,B中每两个数的和作为key,次数作为value写入map,然后查找C,D中每两个数和的相反数是否在map中,如果在,就把 map 中记录的次数累加到结果中。
Java:
public class Solution { public int fourSumCount(int[] A, int[] B, int[] C, int[] D) { int res = 0; HashMap<Integer,Integer> ab = new HashMap<Integer,Integer>(); for(int a:A){ for(int b:B){ ab.put(a+b,ab.getOrDefault(a+b,0) + 1); } } for(int c:C){ for(int d:D){ int part2 = c + d; int part1 = - part2; res += ab.getOrDefault(part1,0); } } return res; } }
Python:
class Solution(object): def fourSumCount(self, A, B, C, D): ans = 0 cnt = collections.defaultdict(int) for a in A: for b in B: cnt[a + b] += 1 for c in C: for d in D: ans += cnt[-(c + d)] return ans
Python: 这个写法牛逼到了只用两行就搞定了
class Solution(object): def fourSumCount(self, A, B, C, D): A_B_sum = collections.Counter(a+b for a in A for b in B) return sum(A_B_sum[-c-d] for c in C for d in D)
C++:
class Solution { public: int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { int res = 0; unordered_map<int, int> m; for (int i = 0; i < A.size(); ++i) { for (int j = 0; j < B.size(); ++j) { ++m[A[i] + B[j]]; } } for (int i = 0; i < C.size(); ++i) { for (int j = 0; j < D.size(); ++j) { int target = -1 * (C[i] + D[j]); res += m[target]; } } return res; } };
类似题目:
All LeetCode Questions List 题目汇总
相关文章
- Leetcode: Remove Duplicate Letters
- Leetcode: Read N Characters Given Read4 II - Call multiple times
- Leetcode: Candy
- [LeetCode][Java] Unique Paths II
- LeetCode高频题46. 全排列
- 【Leetcode】142. 环形链表 II(中等)
- JS Leetcode 264. 丑数 II 题解分析,当暴力无法暴力,让我们弃武从文了解三指针
- [LeetCode] Simplify Path
- 【看懂LeetCode】4. 寻找两个正序数组的中位数
- ChatGPT教程之 04 使用 ChatGPT 解决 Leetcode 难题?
- [LeetCode]5384. 拥有最多糖果的孩子
- 192、【动态规划】leetcode ——64. 最小路径和:回溯法+动态规划(C++版本)
- 178、【数组/动态规划】leetcode ——392. 判断子序列:双指针+动态规划(C++版本)
- 99、【树与二叉树】leetcode ——113. 路径总和 II:回溯法两种版本(C++版本)
- 【LeetCode】122. Best Time to Buy and Sell Stock II
- LeetCode Best Time to Buy and Sell Stock I II III
- leetcode先刷_Pascal's Triangle II
- [LeetCode] 991. Broken Calculator 损坏的计算器
- [LeetCode] Contain Virus 包含病毒
- [LeetCode] 536. Construct Binary Tree from String 从字符串创建二叉树
- [LeetCode] 272. Closest Binary Search Tree Value II 最近的二分搜索树的值之二
- [LeetCode] Word Break II 拆分词句之二
- leetcode 219. Contains Duplicate II 存在重复元素 II(简单)
- leetcode 455. Assign Cookies 分发饼干(简)
- leetcode算法219.存在重复元素 II
- leetcode算法66.加一