tjz*_*zel 8 algorithm time-complexity
我应该以尽可能低的时间复杂度来解决这个问题，但让我更具体一些。
给您一个包含重复项的排序整数数组。
唯一四元组是四个索引的集合。这些索引下的数组中的元素之和必须为给定值 X。例如：
给定一个数组 [10, 20, 30, 40] 且 X = 100，则只有一个四元组：(0, 1, 2, 3)。
给定一个数组 [0, 0, 0, 0, 0] 且 X = 0，则有 5 个四元组： (0, 1, 2, 3), (0, 1, 2, 4), (0, 1, 3 , 4), (0, 2, 3, 4), (1, 2, 3, 4)。
互联网上有很多 N^3 解决方案，但这些解决方案是针对值而不是索引的唯一四元组。在这些解决方案中，示例 1 仍仅给出一个四元组：(10, 20, 30, 40)，但示例 2 只给出一个四元组 (0, 0, 0, 0)，而不是其中的五个。
我找不到一个 O(N^3) 解决方案来代替另一个解决我的问题。我可以轻松地编写一个在 O(N^3logN) 时间内解决该问题的程序。我还听说这个问题的复杂度下限据称是未知的。是否有已知的 O(N^3) 解决方案？
我所知道的解决方案：
明显朴素的方法 O(N^4)：
int solution(int arr[], int arrSize, int X){
int counter = 0;
for(int i=0; i<arrSize-3; ++i)
for(int j=i+1; j<arrSize-2; ++j)
for(int k=j+1; k<arrSize-1; ++k)
for(int l=k+1; l<arrSize; ++l)
if(arr[i] + arr[j] + arr[k] + arr[l] == X)
++counter;
return counter;
}
使用三元组和二分搜索的方法 O(N^3logN)：
int solution(int arr[], int arrSize, int X){
int counter = 0;
for(int i=0; i<arrSize-3; ++i)
for(int j=i+1; j<arrSize-2; ++j)
for(int k=j+1; k<arrSize-1; ++k){
int subX = X - arr[i] - arr[j] - arr[k];
int first = binFirst(subX, arr, k+1, arrSize);
// Binary search that returns the position of the first
// occurrence of subX in arr in range [k+1, arrSize)
// or -1 if not found
int last = binLast(subX, arr, k+1, arrSize);
// Binary search that returns the position of the last
// occurrence of subX in arr in range [k+1, arrSize)
// or -1 if not found
if(first != -1)
counter += last - first + 1;
return counter;
当然，可以通过计算 arr[i]、arr[j]、arr[k] 的所有重复项来改进上述算法，但据我所知，它并没有降低实际的 O(N^3logN) 复杂度。
Python 中的 O(n\xc2\xb2) ，灵感来自\xd7\x92\xd7\x9c\xd7\xa2\xd7\x93 \xd7\x91\xd7\xa8\xd7\xa7\xd7\x9f\ 的答案：
\nfrom itertools import combinations\nfrom collections import Counter\n\ndef solution(arr, X):\n cd = Counter(map(sum, combinations(arr, 2)))\n count = 0\n for i, b in enumerate(arr):\n for d in arr[i+1:]:\n cd[b+d] -= 1\n for a in arr[:i]:\n count += cd[X - (a+b)]\n return count\n叫四元组(a,b,c,d)。我们关注第二个元素，b。对于每个可能的b，我们将每个可能的a（ 左边的元素b）相加，并查找有多少对(c,d)（ 右边的元素b）完成总和a+b+c+d = X，即总和为X - (a+b)。对于该查找，我们有一个哈希映射cd，它将对的总和映射到对的计数。最初，这是整体的所有arr对，但对于b我们考虑的每个，删除其对地图的贡献。
C++ 版本，其中 a/b/c/d 是索引而不是元素：
\nint solution(int arr[], int n, int X){\n std::unordered_map<int, int> cd;\n for (int c=0; c<n; c++)\n for (int d=c+1; d<n; d++)\n cd[arr[c]+arr[d]]++;\n int count = 0;\n for (int b=0; b<n; b++) {\n for (int d=b+1; d<n; d++)\n cd[arr[b]+arr[d]]--;\n for (int a=0; a<b; a++)\n count += cd[X - (arr[a]+arr[b])];\n }\n return count;\n}\n带有测试的Python代码（在线尝试！）：
\nfrom itertools import combinations\nfrom collections import Counter\n\ndef solution(arr, X):\n cd = Counter(map(sum, combinations(arr, 2)))\n count = 0\n for i, b in enumerate(arr):\n for d in arr[i+1:]:\n cd[b+d] -= 1\n for a in arr[:i]:\n count += cd[X - (a+b)]\n return count\n\nimport random\nfrom operator import countOf\n\ndef naive(arr, X):\n sums = map(sum, combinations(arr, 4))\n return countOf(sums, X)\n\narr = random.choices(range(100), k=100)\nprint(naive(arr, 200))\nprint(solution(arr, 200))\n让我们发明解决方案。
\n现在，如果我们创建pairs包含对的总和，例如，
arr = [10, 20, 30, 40]\npairs = [10+20, 10+30, 10+40, 20+30, 20+40, 30+40]\n有一个模式。我们有三对代表 10+x，两对代表 20+x，一对代表 30+x，零对代表 40+x。
\n [10+20, 10+30, 10+40, 20+30, 20+40, 30+40]\n# ------------------- ------------ -----\n\n [30, 40, 50, 50, 60, 70]\n# ---------- ------ --\n所以，总对是
\n3 + 2 + 1\n= sum of first (n-1) natural numbers\n= (n - 1) * (n - 1 + 1) / 2\n= (n - 1) * n / 2\n= (n^2 - n) / 2\n看起来整个pairs数组都会被排序，但事实并非如此。中的那些子数组pairs应该排序，因为初始数组arr已排序。例如，
3 + 2 + 1\n= sum of first (n-1) natural numbers\n= (n - 1) * (n - 1 + 1) / 2\n= (n - 1) * n / 2\n= (n^2 - n) / 2\n现在，让\xe2\x80\x99s 写出pairs原点arr索引
arr = [10, 20, 30, 90]\npairs = [10+20, 10+30, 10+90, 20+30, 20+90, 30+90]\n\n# Those sub-arrays are sorted\n [30, 40, 100, 50, 110, 120]\n# ----------- ------- ---\n(0, 1)和(0, 2)不是有效的四元组，因为我们都有0两对。那么，我们如何才能从逻辑上找到有效的对呢？
我们只有一对有效的对，(0, 1)其中(2, 3)没有0或1
pairs = [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]\n一个事实是，我们总是可以以这样的方式编写四元组：一对紧挨着另一对。例如，
\n [(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]\n# x x x x x x ----\n所以，我们可以通过如下方式来解决问题
\nx = 100\narr = [10, 20, 30, 40]\npairs = [30, 40, 50, 50, 60, 70]\n\n [10, 20, 30, 40]\n# -- ------ --\nquadruple = (10 + 40) + (20 + 30)\n\n# Which can we rewrite as\n [10, 20, 30, 40]\n# ------ ------\nquadruple = (10 + 20) + (30 + 40) = 30 + 70\n\n# Which is as follows\npairs = [30, 40, 50, 50, 60, 70]\n# -- --\n但上面的解决方案是O(n^4)，因为pairs长度(n^2 - n) / 2。
我们可以做得更好，因为我们知道成对的子数组已排序。
\nfor pair0 in pairs:\n valid_pairs_for_pair0 = # Somehow get the valid pairs\n for pair1 in valid_pairs_for_pair0:\n if pair0 + pair1 == x:\n ans += 1\n现在，我们可以通过如下方式解决这个问题。
\narr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] # n = 10\npairs = [\n (0,1),(0,2),(0,3),(0,4),(0,5),(0,6),(0,7),(0,8),(0,9),# (0,x) -> 9 pairs -> 10 - 0 - 1\n (1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),(1,9),# (1,x) -> 8 pairs -> 10 - 1 - 1\n (2,3),(2,4),(2,5),(2,6),(2,7),(2,8),(2,9),# (2,x) -> 7 pairs -> 10 - 2 - 1\n (3,4),(3,5),(3,6),(3,7),(3,8),(3,9),# (3,x) -> 6 pairs -> 10 - 3 - 1\n (4,5),(4,6),(4,7),(4,8),(4,9),# (4,x) -> 5 pairs -> 10 - 4 - 1\n (5,6),(5,7),(5,8),(5,9),# (5,x) -> 4 pairs -> 10 - 5 - 1\n (6,7),(6,8),(6,9),# (6,x) -> 3 pairs -> 10 - 6 - 1\n (7,8),(7,9),# (7,x) -> 2 pairs -> 10 - 7 - 1\n (8,9),# (8,x) -> 1 pair -> 10 - 8 - 1\n]\n\n# We need to find the first valid pair and all of the pairs after that will be valid.\n\nfirst valid pair index for (0, 1) => first (2,x) pair => (2,3) => pairs[9 + 8]\nfirst valid pair index for (0, 2) => first (3,x) pair => (3,4) => pairs[9 + 8 + 7]\nfirst valid pair index for (0, 3) => first (4,x) pair => (4,5) => pairs[9 + 8 + 7 + 6]\n\n# There is a pattern\npairs[9 + 8] => pairs[sum(9 to 1) - sum(7 to 1)]\npairs[9 + 8 + 7] => pairs[sum(9 to 1) - sum(6 to 1)]\npairs[9 + 8 + 7 + 6] => pairs[sum(9 to 1) - sum(5 to 1)]\n\n# That\xe2\x80\x99s how we get started and for binary search\nstart = firstNSum(n - 1) - firstNSum(n - i1 - 2)\nend = start + n - (i1 + 1) - 1 # n - (i1 + 1) - 1 is the number of pairs for (i1,x) pairs\n时间复杂度：O(n^3.log(n)) log(n) + log(n-1) ... log(1) = log(n!) = n.log(n)
空间复杂度：O(n^2)
# For pair0 in pairs:\n # Binary search for all valid sub-arrays of pairs for pair0\n我们可以做得更好。如果我们存储带有总和的对数，同时还存储每个 (i, x) 对组中有多少对pairs
# Loop for i0\n # Loop for i1\n # ans += valid pairs for i0 and i1, which is sum of i1 to n excluding i0 to i1\n时间复杂度：O(n^3)
空间复杂度：O(n^3)
def firstNSum(n):\n return n * (n + 1) // 2\n\ndef binary_search(pairs, x, start, end):\n while start < end:\n mid = (start + end) // 2\n if pairs[mid][1] < x:\n start = mid + 1\n else:\n end = mid\n return start\n\n\ndef count_four_pairs_with_sum(arr, x):\n n = len(arr)\n\n ans = 0\n\n pairs = []\n\n for i0 in range(n - 1):\n for i1 in range(i0 + 1, n):\n curr_sum = arr[i0] + arr[i1]\n pairs.append([(i0, i1), curr_sum])\n\n for [(i0, i1), curr_sum] in pairs:\n\n start = firstNSum(n - 1) - firstNSum(n - i1 - 2)\n end = start + n - (i1 + 1) - 1\n\n while start < len(pairs):\n x_start = binary_search(pairs, x - curr_sum, start, end)\n x_end = binary_search(pairs, x - curr_sum + 1, start, end)\n\n ans += x_end - x_start\n\n i1 += 1\n start += n - i1 - 1\n end = start + n - (i1 + 1) - 1\n\n return ans\n\narr = [10, 20, 30, 40]\nx = 100\nprint(count_four_pairs_with_sum(arr, x))\n如果我们有所有可能对的频率，并且我们寻找每个 的所有有效值，我们可以做得更好（如这个答案所示） 。pair1pair0
设 a + b + c + d = x
\na可以是左边的任意数字b
c并且d可以是任意对b
因为我们知道，我们可以重写任何四元组a < b < c < d，例如，
# Loop for i0\n # Loop for i1\n # ans += valid pairs for i0 and i1, which is sum of i1 to n excluding i0 to i1\n因此，对于任何b我们只需要计算其右侧的有效值(c,d)，这意味着我们不需要考虑任何包含剩余数字的对，b例如(c,d)=(2,5)如果b=4因为2左侧是无效的4
现在，我们可以按如下方式解决这个问题。
\nfrom collections import defaultdict\n\ndef count_four_pairs_with_sum(arr, x):\n n = len(arr)\n\n ans = 0\n\n sum_freq = defaultdict(lambda: defaultdict(int))\n\n for i0 in range(n - 1):\n for i1 in range(i0 + 1, n):\n curr_sum = arr[i0] + arr[i1]\n sum_freq[curr_sum][i0] += 1\n\n for i0 in range(n - 1):\n for i1 in range(i0 + 1, n):\n curr_sum = arr[i0] + arr[i1]\n needed_sum = x - curr_sum\n valid_needed_sum_count = sum([sum_freq[needed_sum][i] for i in range(i1+1, n)])\n ans += valid_needed_sum_count\n\n return ans\n\n\narr = [0, 0, 0, 0, 0]\nx = 0\nprint(count_four_pairs_with_sum(arr, x))\n第一个循环b将继续删除当前的对b，这意味着当b=4我们已经从以前的值中删除所有对时b=1,2,3
时间复杂度：O(n^2)
空间复杂度：O(n^2)
[0, 1, 2, 3, 4, 5, ...., n-1, n]\n# a b c d\n