# 4Sum_2

Oct 04, 2017

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 -2^28 to 2^28 - 1 and the result is guaranteed to be at most 2^31 - 1.

Example:

Input:A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2] Output: 2

Explanation:

The two tuples are:

(0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0

(1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

• sum > 0 -> j–
• sum < 0 -> i++
• sum == 0 -> count++;j–,i++

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int count = 0;
vector<int> v1 (A.size()*B.size() ), v2(C.size()*D.size());
int k = 0;
for(auto c:C)
for(auto d:D)
v2[k++] = c+d;
k = 0;
for(auto a:A)
for(auto b:B)
v1[k++] = a+b;
sort(v1.begin(),v1.end());
sort(v2.begin(),v2.end());
int i = 0,j = v2.size() - 1;
int sum;
while(i < v1.size() && j >= 0){
sum = v1[i] + v2[j];
if (sum > 0)
j--;
else if (sum < 0)
i++;
else {
int k1 = 1,k2 = 1;
//处理重复元素的情况
while(i + 1< v1.size() && v1[i + 1 ] == v1[i]){ k1++; i++; }
while(j > 0 && v2[j-1] == v2[j]) { k2++; j--; }
i++;
j--;
count += k1*k2;
}
}
return count;
}


 int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int>  abSum;
for(auto a : A) {
for(auto b : B) {
++abSum[a+b];
}
}
int count = 0;
for(auto c : C) {
for(auto d : D) {
auto it = abSum.find(0 - c - d);
if(it != abSum.end()) {
count += it->second;
}
}
}
return count;
}


LeetCodeLeetCode

Longest SubString with At Least K Repeating Characters

LongestPalindromicSubString