如何提高Leetcode 4sum-ii挑战的性能

Question

这是一个leet代码竞赛问题,我试图在比赛结束后尝试但我的代码总是超出时间限制.问题是

给定四个列表A,B,C,D的整数值,计算有多少元组(i,j,k,l),使得A [i] + B [j] + C [k] + D [1]是零.

为了使问题更容易,所有A,B,C,D都具有相同的N长度,其中0≤N≤500.
所有整数都在-2 ²⁸到2 ²⁸  - 1 的范围内,结果保证在大多数2 ³¹  - 1.

例:

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

我的代码是

public static int FourSumCount(int[] A, int[] B, int[] C, int[] D)
    {
        int count = 0;
        List<int> map1 = new List<int>();
        List<int> map2 = new List<int>();

        for (int i = 0; i < A.Length; i++)
            for (int y = 0; y < B.Length; y++)
            {
                map1.Add(A[i] + B[y]);
                map2.Add(C[i] + D[y]);
            }
        for (int i = 0; i < map2.Count(); i++)
        {
            for (int j = 0; j < map2.Count(); j++)
                //if (map1.Contains(map2[i]*-1))
                //{
                //    var newList = map1.FindAll(s => s.Equals(map2[i] * -1));
                //    count = count + newList.Count();
                //}
                if (map1[i] + map2[j] == 0)
                {
                    count++;
                }
        }


        return count;
    }

有没有更好的方法？谢谢你的期待.

Answer 1

你的第一步没问题。但是使用Dictionary代替Listwhich 将确保恒定的时间查找并降低第二部分的复杂性。

这是我的 C++O(n^2)解决方案：

int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
    int n = A.size();
    int result = 0;
    unordered_map<int,int> sumMap1;
    unordered_map<int,int> sumMap2;

    for(int i = 0; i < n; ++i) {
        for(int j = 0; j < n; ++j) {
            int sum1 = A[i] + B[j];
            int sum2 = C[i] + D[j];
            sumMap1[sum1]++;
            sumMap2[sum2]++;
        }
    }
    for(auto num1 : sumMap1) {
        int number = num1.first;
        if(sumMap2.find(-1 * number) != sumMap2.end()) {
            result += num1.second * sumMap2[-1 * number];
        }
    }
    return result;
}

核心观察是 - 如果W + X + Y + Z = 0那么W + X = -(Y + Z)。

在这里，我对 (A, B) 和 (C, D) 中的每个可能的总和使用了两个哈希表，查找该总和的出现次数。

然后，对于每个sum(A, B)我们可以找到是否sum(C, D)包含将确保sum(A, B) + sum(C, D) = 0. 将（出现的次数sum(a, b)）*（互补的出现次数sum(c,d)）添加到结果中。

创造sum(A, B)和sum(C, D)需要O(n^2)时间。计算元组的数量是O(n^2)因为n^2每个对（A-B，C-D）的总和。其他操作如在哈希表上的插入和搜索被摊销O(1)。因此，总时间复杂度为O(n^2)。

Answer 2

我建议在中间算法中相遇：

 A[i] + B[j] + C[k] + D[l] = 0

其实就是找出A[i] + B[j]并C[k] + D[l]使得

 (A[i] + B[j]) == (-C[k] - D[l])

我们可以将所有可能的A[i] + B[j]总和放入一个字典中，然后在循环中-C[k] - D[l]尝试在该字典中查找。你可以像这样实现它：

  private static int FourSumCount(int[] A, int[] B, int[] C, int[] D) {
    // left part: all A[i] + B[j] combinations
    Dictionary<int, int> left = new Dictionary<int, int>();

    // loop over A[i] + B[j] combinations
    foreach (var a in A)
      foreach (var b in B) {
        int k = a + b;
        int v; 

        if (left.TryGetValue(k, out v))  
          left[k] = v + 1; // we have such a combination (v of them)
        else 
          left.Add(k, 1);  // we don't have such a combination
      }

    int result = 0;

    // loop over -C[k] - D[l] combinations
    foreach (var c in C)
      foreach (var d in D) {
        int v;

        if (left.TryGetValue(-c - d, out v)) 
          result += v;
      } 

    return result;
  }

正如你所看到的，我们有O(|A| * |B| + |C| * |D|)复杂性；万一A，B，C和D阵列具有大致相等尺寸N的复杂性是O(N**2)。