Làm thế nào để cải thiện hiệu suất của Leetcode 4sum-ii thách thức

Question

Đó là một cuộc thi mã Leet question mà tôi đang cố gắng thử sau khi cuộc thi kết thúc nhưng mã của tôi luôn vượt quá giới hạn thời gian. Câu hỏi là

Với bốn danh sách A, B, C, D của các giá trị số nguyên, tính toán bao nhiêu tuples (i, j, k, l) có là như vậy mà A [i] + B [j] + C [k] + D [l] bằng không.

Để làm cho vấn đề một chút dễ dàng hơn, tất cả A, B, C, D có cùng chiều dài của N trong đó 0 ≤ N ≤ 500.
Tất cả các số nguyên là trong khoảng -2 -2  - và kết quả được đảm bảo tối đa là 2   -   1.

Ví dụ:

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 

Mã của tôi là

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; 
    } 

được Có cách nào tốt hơn? Cảm ơn với sự mong đợi.

Answer 1

Tôi đề nghị loại gặp nhau trong thuật toán giữa:

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

thực sự có nghĩa là để tìm hiểu A[i] + B[j] và C[k] + D[l] mà

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

Chúng ta có thể đặt tất cả các thể A[i] + B[j] khoản tiền vào một từ điển và sau đó, trong vòng lặp qua -C[k] - D[l], hãy tìm kiếm trong từ điển này. Bạn có thể triển khai như sau:

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; 
    } 

Như bạn có thể thấy, chúng tôi có độ phức tạp O(|A| * |B| + |C| * |D|); trong trường hợp các ô A, B, C và D có kích thước xấp xỉ bằng nhau N độ phức tạp là O(N**2).

Answer 2

Bước đầu tiên của bạn là ổn. Nhưng sử dụng Dictionary thay vì List để đảm bảo tra cứu thời gian không đổi và giảm độ phức tạp của phần thứ hai.

Đây là C++ của tôi O(n^2) giải pháp:

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; 
} 

Các quan sát lõi là - nếu W + X + Y + Z = 0 sau đó W + X = -(Y + Z).

Ở đây tôi đã sử dụng hai bảng băm cho mỗi khoản tiền có thể có trong cả hai (A, B) và (C, D) tìm số lần xuất hiện của tổng này.

Sau đó, đối với mỗi sum(A, B), chúng tôi có thể tìm thấy nếu sum(C, D) chứa số tiền miễn phí sẽ đảm bảo sum(A, B) + sum(C, D) = 0. Thêm (số lần xuất hiện của sum(a, b)) * (số lần xuất hiện miễn phí sum(c,d)) vào kết quả.

Tạo sum(A, B) và sum(C, D) sẽ mất O(n^2) thời gian. Và đếm số lượng bộ là O(n^2) vì có tổng số n^2 cho mỗi cặp (A-B, C-D). Các hoạt động khác như chèn và tìm kiếm trên hashtable được khấu hao O(1). Vì vậy, tổng thời gian phức tạp là O(n^2).