Source: InterviewBit – Largest Continuous Sequence Zero Sum

Find the largest continuous sequence in a array which sums to zero.

Example:

Input:  {1 ,2 ,-2 ,4 ,-4}
Output: {2 ,-2 ,4 ,-4}

NOTE : If there are multiple correct answers, return the sequence which occurs first in the array.

解題：

  1. 這題如果不取巧的話也並不困難，就是把所有長度組合都試過一次，看哪個頭尾組合的合計值是0並取長度最長者，順序由前至後便可避免取到不符輸出條件的子陣列，複雜度則為O(n^2)；
  2. 但除了暴力解以外，是否還有什麼更方便快速的解法呢？ 
    換個角度想，如子陣列合計數 sum(L[i:j]) == 0
即表示 L[i] + sum(L[i+1:j]) == 0
以及 L[i-1] == sum(L[i-1 : j])

    得到這層關係後，就可以嘗試用 hashmap 來解題了：

  3. 但具體應該怎麼做呢？很簡單，採用一個迴圈並依序把累計至今的合計數用 hashmap 對應索引值，而當 hashmap 找到已經建立過連結的 key: value 對應時表示我們找到了一組 sum(L[i:j]) == 0，此時再計算子陣列長度是否長於截至目前所能找到的最長子陣列，如是則進行輸出值之替換。用此作法則可以將複雜度降低至O(n)；
  4. 在用此法解題時需另外注意的是，合計值為 0 時的處理方式：在 hashmap 沒有預設值的情況下當發生合計值為 0 時會因為此算法的機制而另外建立一組 key: value 對應，但此合計數代表的是 sum(L[:i]) == 0，故在一開始建立 hashmap 時便應考量此情形，並預設合計值 0 的起始對應索引值（筆者因個人程式碼機制設計，將其設為 -1 ）。

Code:

class Solution:
	# @param A : list of integers
	# @return a list of integers
	def lszero(self, A):
	    """
	    Find j - i maximized with sum(A[i:j]) == 0
	    sum(A[i:j]) == 0 => sum(A[:j]) = sum(A[:i-1])
	    """
	    hashSum = {0:-1}
	    temp, maxL, comb = 0, 0, []
	    for i in range(len(A)):
	        temp += A[i]
	        try:
	            if ((i+1) - hashSum[temp] > maxL):
	                maxL = (i+1) - hashSum[temp]
	                comb = A[hashSum[temp]+1:i+1]
	        except:
	            hashSum[temp] = i
            return comb

GitHub: GitHub

發表留言