如題：

給定四個包含整數的數組列表?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 。所有整數的范圍在 -228 到 228 - 1 之間，最終 結果不會超過?231 - 1 。例如: 輸入: A = [ 1, 2] B = [-2,-1] C = [-1, 2] D = [ 0, 2]輸出: 2 解釋: 兩個元組如下: 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

這道題在hash專項練習里遇到，最初的方法是循環法(俗稱暴力)，遍歷4個數組，計算每種組合，時間復雜度在O(n^4)。復雜度還蠻大的，應該可以優化，想了半天，沒想到啥巧妙的方法。看了其它人的題解，可以優化到O(n^2)，思路：遍歷AB數組，計算每種組合的和，將和放入到hash桶中，key為和，值為次數。時間復雜度為O(n^2)。接著遍歷CD數組，計算各種組合s，查找hash中是否存在-s，找到則累積可能性。時間復雜度為O(n^2)。總的時間復雜度為O(2n^2)。和O(n^4)相比，的確優化了不少。hash需要占空間，空間換時間，不虧。思路倒是很簡單，但是的確是沒想到，其實就是減少內層循環的次數。遇到同樣的題型都可以如此優化。有學會一招。下面是是c語言的解法：

/** 解法1：暴力遍歷，O(n^4)* 解法2：使用hash優化暴力算法，O(n^2)*/typedef struct hlist {int nkey, pkey;int nNum, pNum;struct hlist *next; }*hnode;hnode newHashNode(int key) {hnode n = (hnode)calloc(1, sizeof(struct hlist));if (key < 0){n->nkey = key;n->pkey = 0 - key;n->nNum = 1;}else{n->pkey = key;n->nkey = 0 - key;n->pNum = 1; if (key == 0)n->nNum = 1;}return n; }int hashKey(int s) {if (s < 0)return (0 - s) % 10000;elsereturn s % 10000; }int fourSumCount(int* A, int ASize, int* B, int BSize, int* C, int CSize, int* D, int DSize){int i,j,n = 0,s, key;hnode hash[10000] = {0}, prev, curr, new;//特殊情況處理if (ASize == 0 || BSize == 0 ||CSize == 0 || DSize == 0)return 0;//遍歷AB和，將其加入到hash桶中，和為key，值為次數for (i = 0; i < ASize; i++){for (j = 0; j < BSize; j++){s = A[i] + B[j];key = hashKey(s);prev = NULL;curr = hash[key];while (curr){if (curr->nkey == s){curr->nNum++;break;}else if (curr->pkey == s){curr->pNum++;break;}else{prev = curr;curr = curr->next;}}if (!curr){new = newHashNode(s);if (prev)prev->next = new;elsehash[key] = new;} }}//遍歷CD和s，在hash表中查找-s，統計次數。for (i = 0; i < CSize; i++){for (j = 0; j < DSize; j++){s = C[i] + D[j];s = 0 - s;key = hashKey(s);curr = hash[key];while (curr){if (curr->nkey == s){n += curr->nNum;break;} else if (curr->pkey == s){n += curr->pNum;break;} elsecurr = curr->next;}}}return n; }

?

=============================================================================================

Linux應用程序、內核、驅動開發交流討論群(745510310)，對后端、互聯網感興趣的同學可以加群討論、交流、資料查找等，前進的道路上，你不是一個人奧^_^。
---------------------?
版權聲明：本文為CSDN博主「mrsonko」的原創文章，遵循CC 4.0 by-sa版權協議，轉載請附上原文出處鏈接及本聲明。
原文鏈接：https://blog.csdn.net/fuyuande/article/details/99434278

總結

以上是生活随笔為你收集整理的leetcode 454. 四数相加 II c语言的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。