2020年6月15日 星期一

Leetcode題解 Python：Find Two Non-overlapping Sub-arrays Each With Target Sum

給一個正整數陣列 arr ，跟一整數 target ，最找出二子陣列各自總和皆為target且二子陣列不重壘的最小長度總和。若沒有回傳 -1。

關於找子陣列(注意要為連續的或是稱序列)總和為target，通常用計算其累進值，accu[0] = arr[0], accu[1] = accu[0] + arr[0], accu[-1] = sum(arr)。
如果 accu[i] - target 在 accu 內，就代表有對應另外一個的連續子陣列存在。透過 accu[j] - accu[i] 可以找到 arr 任位置的連續子陣列總和。

在計算累進值的同時，就可以開始找目標值，也是這種算法的優勢，如果搭配 hash類 的查詢，只要累進值算完，就能找完所有可能，相當於 O(N) Time。 

首先要決定 ans 的預設值，因為如果拿 -1 當預設去比小，最後會是 -1 ，需要找一個比 -1 大且不會有可能出現的值，最大可能為 len(arr)，所以 ans 預設為 len(arr) + 1。

一旦有 accu[i] - target 出現，表示現在到找一段總和為 target，這一段的頭位置為 accu[i] - target 在 accu 中的位置，尾位置為 i 。
如果前面已經有一段，只要前一段的尾位置 >= 這一段的頭位置，代表兩者沒有重壘到，就能拿二段長度相交去更新 ans 。

每個找到的子陣列其尾位置(i)是最先被知道的，之後的找到的子陣列只要其頭位置在此或之後，都可以與之形成合格的可能總長度。
如在 i 位置上找到總長度最短的 shortest，在 i 位置之後的找到每段其頭位置在 i 或 i 之後，都能與 shortest 組合起來。
因此可這麼看，在i與之後的位置最小長都是 shortest。

每個位置都有一個 shortest，整體用 shortests 紀錄。
shortests [i] 為頭位置在 i 時能組合最小的長度。

每位置不論有沒有找到，都要把 shortest 保存在 shortests [i]。
(※shortest: [default,s1,s1,s1,s2,s2,s2,s2,s3,...,shortest] )

找到一段，就用該段的頭位置 headPos 去對 shortest[headPos] 得到前方可組合的最小長度，二者長度相加去更新ans。
shortest 預設也為 len(arr)+1 ，如果前方沒有找到或沒能組合的，也不會改動 ans。

Python 
class Solution:
    def minSumOfLengths(self, arr: List[int], target: int) -> int:
        accuPos = {0:-1}
        accu = 0
        ans = shortest = len(arr)+1 
        shortests = [len(arr)+1] * len(arr)    
        for i, num in enumerate(arr):
            accu += num
            accuPos[accu] = i
            if accu - target in accuPos:                   
                length = i - accuPos[accu - target] 
                if accuPos[accu - target] > -1:
                    ans = min(ans, length + shortests[accuPos[accu - target]])                              
                shortest = min(shortest, length)
            shortests[i] = shortest
        return -1 if ans == len(arr)+1 else ans
於
標籤： ,