Source: 4 Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

  • Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
  • The solution set must not contain duplicate quadruplets.

Example :
Given array S = {1 0 -1 0 -2 2}, and target = 0
A solution set is:

    (-2, -1, 1, 2)
    (-2,  0, 0, 2)
    (-1,  0, 0, 1)

Also make sure that the solution set is lexicographically sorted.
Solution[i] < Solution[j] iff Solution[i][0] < Solution[j][0] OR (Solution[i][0] == Solution[j][0] AND ... Solution[i][k] < Solution[j][k])

解題：

  1. 這題也是非常適合採用暴力解，套入四個迴圈即可完成。但O(n^4)光看就覺得很嚇人，有什麼方法可以降低複雜度加快處理速度呢？
  2. 因為題目要求組合不應重複，且 a <= b <= c <= d 條件必須成立，故對陣列先執行排序確立大小關係有助於後續篩選及運算進行；
  3. 再來是根據題目給予之條件 
    S[i] + S[j] + S[k] + S[l] = T , i < j < k < l

    也就是說

    T - (S[i] + S[j]) = S[k] + S[l]

    依據這層關係，便可以先用兩層迴圈得到 S[i] 跟 S[j] 的組合，此處可以先用hashmap來排除 [S[i], S[j]] 的重複組合。而 [S[k], S[l]] 這個組合要怎麼做才能達到降低複雜度的目的呢？

  4. 因我們可以依題目條件得知 
    T - (S[i] + S[j]) - (S[k] + S[l]) = 0

    而且陣列已經過適當排序，此時便可採用從兩端最大最小值來進行比較移動：

    預設 k = j+1, l = n-1,
在 k < l 的情況下
如 T - (S[i] + S[j]) - (S[k] + S[l]) > 0
表示S[l]值太大（因S[k]已在最左端，不能再更小）
應調整 l 值；
如 T - (S[i] + S[j]) - (S[k] + S[l]) < 0
表示S[k]值太小（因S[l]已在最右端，不能再更大）
應調整 k 值
  5. 最後則應注意在得到合適的子陣列值後後續應如何推進序列值 k, l 而不造成重複以及無法結束迴圈之狀況。

Code:

from collections import defaultdict
class Solution:
    # @param S : list of integers
    # @param T : integer
    # @return a list of list of integers
    def fourSum(self, S, T):
        #since condition a<=b<=c<=d must be applied
        S.sort()
        sumMatch = defaultdict(list)
        n, output = len(S), []
        for i in range(n-3):
            for j in range(i+1, n-2):
                #T-(S[i]+S[j]) == S[k]+S[l]
                if [S[i], S[j]] in sumMatch[T-S[i]-S[j]]:
                    continue
                sumMatch[T-S[i]-S[j]].append([S[i], S[j]])
                target = T-S[i]-S[j]
                k, l = j+1, n-1
                while k < l:
                    if target-S[k]-S[l] > 0:
                        k += 1
                    elif target-S[k]-S[l] < 0:
                        l -= 1
                    else:
                        output.append([S[i],S[j],S[k],S[l]])
                        while S[k] == S[k+1] and k+1 < l:
                            k += 1
                        while S[l] == S[l-1] and l-1 > k:
                            l -= 1
                        k += 1
                        l -= 1
        return output

GitHub: GitHub

發表留言