子序列總數

Question

給定一個整數數組，例如[1, 2, -3, 1]查找是否存在與0相加的子序列並返回它（例如[1, 2, -3]或[2, -3, 1]）。
檢查每個子序列的效率太低，爲O(n^2)。任何改進想法？

Answer 1

創建一個新的數組，每個元素等於之前元素加上那個元素的總和。

輸入：

1 4 -3 -4 6 -7 8 -5 

變爲：

1 5 2 -2 4 -3 5 0 
^   ^

然後尋找匹配所得數組中的元素。因爲它們代表函數整體變化爲零的位置，你會發現如果它們的位置是i和k，那麼子序列（i + 1，k）就是一個零和子序列。 （在這種情況下，[2：6]）。

此外，表中的任何零指示子序列（0，k）是零和子序列。對於查找，散列表或其他快速碰撞定位器使得該O（N）能夠執行。

Answer 2

做的運行總和，在哈希表中存儲和值與數組索引

沿着如果你有機會，你已經看到了一個和值，返回1 +索引在哈希表，以及當前指數。 此解決方案是O（n）時間複雜性。

不需要新的陣列。由於散列，空間複雜度爲O（N）。

---

Python實現：

input = [1, 4, -3, -4, 6, -7, 8, -5] 
map = {} 
sum = 0 
for i in range(len(input)): 
    sum += input[i] 
    if sum in map: 
     print map[sum][0] + 1, "to", i 
    map[sum] = (i, sum) 

注意，重複的子序列中未示出，例如： 如果（1至2）是一個子序列和（3至4），（1〜4 ）將不會顯示。您可以通過在地圖上的每個位置存儲列表實現這一行爲：

for x in map[sum]: 
    print x[0]+1, "to", i 
map[sum].append((i, sum)) 

Answer 3

A C++實現類似於法布里西奧的回答邏輯。

pair<int, int> FindSubsequenceSum(const vector<int>& arr)  
{ 
    map<int, int> sumMap; 
    map<int, int>::iterator it; 
    int sum = 0; 
    for (int i = 0; i < arr.size(); i++) 
    { 
    sum += arr[i]; 
    it = sumMap.find(sum); 
    if (it != sumMap.end()) 
    { 
     return make_pair(it->second + 1, i); 
    } else { 
     sumMap.insert(make_pair(sum, i)); 
    } 
} 

int main() 
{ 
    int arr[] = {1,4,-3,-4,6,-7,8,-5}; 
    vector<int> input(arr, arr + sizeof(arr)/sizeof(arr[0])); 
    pair<int, int> result = FindSubsequenceSum(input); 

    cout << "(" << result.first << "," << result.second << ")" << endl; 

    return 0; 
} 

Output: 
(2,6) 

Answer 4

下面是Java實現的解決方案通過@Fabricio

建議

public static int countAllSubSequenceForZeroSum(int[] array) { 
    int count = 0; 
    Map<Integer, Integer> encounteredSum = new HashMap<>(); 
    int prev = array[0]; 
    if(prev == 0) { 
     count++; 
     System.out.println("Found at index: "+0); 
    } 
    for (int i = 1; i < array.length; i++) { 
     prev += array[i]; 
     if(encounteredSum.containsKey(prev)) { 
      System.out.println("Found at index: "+i+ " start index: "+encounteredSum.get(prev)); 
      printSequenceForZeroSum(array, i); 
      count++; 
     } else { 
      encounteredSum.put(prev, i); 
     } 
    } 
    return count; 
} 

public static void printSequenceForZeroSum(int[] array, int endIndex) { 
    int sum = array[endIndex]; 
    while(sum!=0) { 
     System.out.print(array[endIndex]+ " "); 
     sum += array[--endIndex]; 
    } 
    System.out.println(array[endIndex]); 
}