題目描述：
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
一刷題解（Dictionary）：
這一題我們在四個數組中找出有多少個索引的組合可以使用四個數組提取出的元素相加結果為0。我最開始看到的時候是非常懵的，還想著怎麼用遞歸來做，但是實在是絞盡腦汁都想不出來遞歸可以怎麼寫，就連breaking Point都想不出來，最後還是去Google了一下。
Google完之後，看到其他大神的思路和解法發現自己還是太過於執著「A[i] + B[j] + C[k] + D[l] = 0」 這個公式，非得要找到i, j, k, l不可。但是原來是不需要這樣做的，這個公式可以巧變成：A[i] + B[j] = -(C[k] + D[l])。這樣一來，不但解法上更直觀易懂，時間複雜度也從原來的O(n^4) 減到了 O(n^2)。
在A[i] + B[j] = -(C[k] + D[l])的情況下，我們要做的就是建立起A[i] + B[j] 和 -(C[k] + D[l])之間的對應關係，要建立對應關係就離不開Dictionary了。我們可以建立一個Key為A[i] + B[j]的和，Value為這個和出現的次數的字典。首先先遍歷A和B，將A和B所有的和(A[i] + B[j])以及該和的出現頻次加到字典裡，然後再遍歷C和D。
由於A[i]+B[j] = -(C[k] + D[l])，因此我們可以直接嘗試通過-(C[k] + D[l])向字典取值，如果字典存在這個鍵，就代表有與出現頻次這麼多次的情況A[i] + B[j] + C[k] + D[l] = 0。
public class Solution {
public int FourSumCount(int[] A, int[] B, int[] C, int[] D) {
//A[i] + B[j] + C[k] + D[l] = 0
//A[i] + B[j] = -(C[k] + D[l])
//Key:Sum of A[i]+B[j] ; Value:Frequencies of this Sum
Dictionary<int, int> sumOfAB = new Dictionary<int, int>();
//記錄A和B的元素和
for (int i = 0; i < A.Length; i++)
{
for (int j = 0; j < B.Length; j++)
{
int sum = A[i] + B[j];
if (!sumOfAB.ContainsKey(sum))
{
sumOfAB.Add(sum, 0);
}
sumOfAB[sum]++;
}
}
int zeroFreq = 0;
//檢查-(C + D)的元素是否存在於AB字典裡
for (int k = 0; k < C.Length; k++)
{
for (int l = 0; l < D.Length; l++)
{
int sum = C[k] + D[l];
if (sumOfAB.ContainsKey(-sum))
{
//在的話就代表有sumOfAB[-sum]這麼多次的A[i] + B[j] + C[k] + D[l] = 0出現
zeroFreq += sumOfAB[-sum];
}
}
}
return zeroFreq;
}
}