Source: InterviewBit – Equal

Given an array A of integers, find the index of values that satisfy A + B = C + D, where A,B,C & D are integers values in the array

Note:

1) Return the indices `A1 B1 C1 D1`, so that 
  A[A1] + A[B1] = A[C1] + A[D1]
  A1 < B1, C1 < D1
  A1 < C1, B1 != D1, B1 != C1 

2) If there are more than one solutions, 
   then return the tuple of values which are lexicographical smallest. 

Assume we have two solutions
S1 : A1 B1 C1 D1 ( these are values of indices int the array )  
S2 : A2 B2 C2 D2

S1 is lexicographically smaller than S2 iff
  A1 < A2 OR
  A1 = A2 AND B1 < B2 OR
  A1 = A2 AND B1 = B2 AND C1 < C2 OR 
  A1 = A2 AND B1 = B2 AND C1 = C2 AND D1 < D2

Example:

Input: [3, 4, 7, 1, 2, 9, 8]
Output: [0, 2, 3, 5] (O index)

If no solution is possible, return an empty list.

解題：

  1. 這題使用暴力解法自然是套用 4 個 for 迴圈找到所有 A[A1] + A[B1] = A[C1] + A[D1]的組合，而這方法會導致 TLE 也是完全可預見的；
  2. 稍微簡化一些的做法是把等式轉成 A[A1] + A[B1] - A[C1] = A[D1]，並建立 hashmap 儲存等式左半邊的資訊。這方法可將複雜度從原本的 O(n^4) 降至 O(n^3)，但仍顯不足；
  3. 那，如果先找出所有A[i] + A[j]的組合並將有相同加總數的分在同一類，再依類別進行比較呢？如此一來就可以將複雜度降至 O(n^2) ，但有許多面向需要注意：
    1. 不同類別因序列值組合不盡相同，故對於符合輸出門檻的值均需要執行 S1 vs S2 的比較確認輸出值是否需要更換；
    2. A1, B1, C1, D1 的大小次序條件必須確認清楚以避免輸出產生錯誤。
  4. 另外要注意一個部份是如將所有符合條件的序列值組合 [i, j] 全數加入，在進行比對時仍有可能因組合數量太多導致 TLE。故筆者後來將 3.b 的確認門檻移至在尋找A[i] + A[j]組合時即同步執行，並且依據 for 迴圈由小至大歷遍序列值的機制，來將所有相同加總數的組合限縮至不超過 2 組，減少評估是否要更換輸出值時不必要的比較程序。

Code:

from collections import defaultdict
class Solution:
    # @param A : list of integers
    # @return a list of integers
    def equal(self, A):
        n, output = len(A), []
        pairwiseSum = defaultdict(list)
        for i in range(n-1):
            for j in range(i+1, n):
                if len(pairwiseSum[A[i]+A[j]]) == 0: pass
                elif len(pairwiseSum[A[i]+A[j]]) >= 2: continue
                #restrictions: A1 < B1, C1 < D1
                #A1 < C1, B1 != D1, B1 != C1
                elif (i <= pairwiseSum[A[i]+A[j]][0][0]) or (
                    pairwiseSum[A[i]+A[j]][0][1] == i) or (
                    pairwiseSum[A[i]+A[j]][0][1] == j):
                    continue
                pairwiseSum[A[i]+A[j]].append([i, j])
        for val in pairwiseSum.values():
            if len(val) < 2: continue
            if not output: pass
            elif (val[0][0] < output[0]): pass
            elif (val[0][0] > output[0]): continue
            elif (val[0][1] < output[1]): pass
            elif (val[0][1] > output[1]): continue
            elif (val[1][0] < output[2]): pass
            elif (val[1][0] > output[2]): continue
            elif (val[1][1] < output[3]): pass
            elif (val[1][1] > output[3]): continue
            output = [val[0][0], val[0][1], val[1][0], val[1][1]]
        return output

GitHub: GitHub

發表留言