4Sum II问题及解法

xiaoxiao2021-02-28  85

问题描述:

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.

示例:

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

问题分析:

为了节约时间,我们可以考虑将时间缩至O(n^2)。将A和B的元素值之和保存下来,然和根C和D的元素之和比较,看相加是否为零,把为零的组合保存下来。最后求得总数。

过程详见代码:

class Solution { public: int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) { unordered_map<int,int> absum; int res = 0; for(auto a : A){ for(auto b : B){ absum[a+b]++; } } for(auto c : C){ for(auto d : D){ if(absum.count(-c-d) != 0){ res += absum[-c-d]; } } } return res; } };

转载请注明原文地址: https://www.6miu.com/read-59718.html

最新回复(0)