arrays - 数组中的四元组满足约束

Question

在正整数数组 A[1...n] 中，您要计算数组中满足以下条件的所有四元组:

A[i] + A[j] + A[k] = A[l] where 1 <= i < j < k < l <=n 

我尝试了很多东西，但找不到比 O(n^3logn)

更好的解决方案

我们能否在 O(n^3) 或 O(n^2) 中解决它以满足索引的排序约束？

Answer 1

为什么不是 O(n^2)？如果我们有

A[i] + A[j] + A[k] = A[l]
  where 1 ≤ i < j < k < l ≤ n

然后我们散列所有

A[i] + A[j] pairs
   where 1 ≤ i < j < n - 1

然后我们可以迭代:

l = n
k = n - 1

check if A[l] - A[k] is in the hash

现在在我们下降时更新每个元素:

j = n - 2

remove each instance of A[j] + A[i] in the hash
  where 1 ≤ i < j

for each instance of A[l] - A[j]
  where j < l < n
  check if a value exists in the hash

j = j - 1
...

尝试使用 JavaScript:

function f(A){
  if (A.length < 4)
    return 0;
  let n = A.length;
  let hash = {};
  let i = 0;
  let j;
  let k;
  let l;
  let sum;
  let diff;
  let count = 0;
  
  // Hash sums up to A[n - 3]
  // in O(n^2) time
  for (; i<n-3; i++){
    for (j=i+1; j<n-2; j++){
      sum = A[i] + A[j];
      hash[sum] = hash[sum] ? hash[sum] + 1 : 1;
    }
  }

  diff = A[n-1] - A[n-2];
  if (hash[diff])
    count = count + hash[diff];
  
  // Iterate on j descending,
  // updating the hash each time,
  // O(n) times
  for (; j>1; j--){
    // Remove instances of j in
    // the hash in O(n) time
    for (i=j-1; i>=0; i--){
      sum = A[i] + A[j];
      hash[sum] = hash[sum] - 1;
    }
    
    // Check for valid quadruples
    // in O(n) time
    // where the old j is now k
    k = j;
    for (l=k+1; l<n; l++){
      diff = A[l] - A[k];
      if (hash[diff])
        count = count + hash[diff];
    }
  }
  
  return count;
}

/*
1 1 1 1 3 3

x x x   x
x x x     x
x x   x x
x x   x   x
x   x x x
x   x x   x
  x x x x
  x x x   x
  
Total 8
*/
var A = [1,1,1,1,3,3];
console.log(JSON.stringify(A))
console.log(f(A));