數組和set都靠邊站！
❞第454題.四數相加II給定四個包含整數的數組列表 A , B , C , D ,計算有多少個元組 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
為了使問題簡單化，所有的 A, B, C, D 具有相同的長度 N，且 0 ≤ N ≤ 500 。所有整數的範圍在 -2^28 到 2^28 - 1 之間，最終結果不會超過 2^31 - 1 。
「例如:」
輸入:A = [ 1, 2]B = [-2,-1]C = [-1, 2]D = [ 0, 2]
輸出:2
「解釋:」
兩個元組如下:
(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思路本題咋眼一看好像和第18題. 四數之和，第15題.三數之和差不多，其實差很多。
「本題是使用哈希法的經典題目，而第18題. 四數之和，第15題.三數之和 並不合適使用哈希法」，因為三數之和和四數之和這兩道題目使用哈希法在不超時的情況下做到對結果去重是很困難的，很有多細節需要處理。
「而這道題目是四個獨立的數組，只要找到A[i] + B[j] + C[k] + D[l] = 0就可以，不用考慮有重複的四個元素相加等於0的情況，所以相對於題目18. 四數之和，題目15.三數之和，還是簡單了不少！」
如果本題想難度升級：就是給出一個數組（而不是四個數組），在這裡找出四個元素相加等於0，答案中不可以包含重複的四元組，大家可以思考一下，後續的文章我也會講到的。
本題解題步驟：
首先定義 一個unordered_map，key放a和b兩數之和，value 放a和b兩數之和出現的次數。遍歷大A和大B數組，統計兩個數組元素之和，和出現的次數，放到map中。定義int變量count，用來統計a+b+c+d = 0 出現的次數。在遍歷大C和大D數組，找到如果 0-(c+d) 在map中出現過的話，就用count把map中key對應的value也就是出現次數統計出來。C++代碼class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int, int> umap; //key:a+b的數值，value:a+b數值出現的次數
// 遍歷大A和大B數組，統計兩個數組元素之和，和出現的次數，放到map中
for (int a : A) {
for (int b : B) {
umap[a + b]++;
}
}
int count = 0; // 統計a+b+c+d = 0 出現的次數
// 在遍歷大C和大D數組，找到如果 0-(c+d) 在map中出現過的話，就把map中key對應的value也就是出現次數統計出來。
for (int c : C) {
for (int d : D) {
if (umap.find(0 - (c + d)) != umap.end()) {
count += umap[0 - (c + d)];
}
}
}
return count;
}
};
歡迎在評論區留言討論！
我將算法學習相關的資料已經整理到了Github ：https://github.com/youngyangyang04/leetcode-master，裡面還有leetcode刷題攻略、各個類型經典題目刷題順序、思維導圖看一看一定會有所收穫！
因為公眾號改版，時間線被打亂，一些精彩文章大家可能錯過了。如果感覺這裡的文章對你有幫助，趕緊給「代碼隨想錄」加一個星標吧，方便第一時間閱讀文章。每天8:35準時推送一道經典算法題目，助你輕鬆學習算法！