零和子陣

Question

數組包含正反兩方面的因素，查找其 總和等於0

Answer 1

在目前接受的答案的鏈接需要註冊爲會員，我不其內容的子陣。

該算法將找到總和爲0的所有子陣列，並且可以很容易地修改它以找到最小值或跟蹤開始和結束索引。該算法是O（n）。

給定一個int[] input陣列，則可以創建一個int[] tmp陣列，其中tmp[i] = tmp[i - 1] + input[i]; TMP中的每個元素將輸入的總和存儲多達該元素（數組的前綴總和）。

現在，如果您檢查tmp，您會注意到可能存在彼此相等的值。假設這個值在索引j an k with j < k處，那麼直到j的輸入的總和等於直到k的總和，這意味着j和k之間的數組部分的總和爲0！具體來說，0和子數組將從索引j + 1到k。

• 注意：如果j + 1 == k，那麼k is 0就是這樣！ ;）
• 注意：該算法應考慮虛擬tmp[-1] = 0;
• 注意：一個空數組的總和爲0，它很小，這個特殊情況應該在面試中提出。然後面試官會說這不算，但那是另一個問題！ ;）

可以用不同的方法完成實現，包括使用HashMap和pair，但要注意上面註釋部分中的特例。

實施例：

int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2} 
int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5} 

• 值4在TMP在索引0和3 ==>總和TMP 1至3 = 0，長度（3 - 1）+ 1 = 3
• 值0在tmp的索引5 ==> sum tmp 0到5 = 0，length（5-0）+ 1 = 6
• tmp在索引6和7的值3 ==> sum tmp 7 to 7 = 0，length （7 - 7）+ 1 = 1

**** UPDATE ****

假設在我們的tmp數組中，我們最終得到了具有相同值的多個元素，那麼您必須考慮其中的每個相同對！實施例（記住虛擬「0」在索引「-1」）：

int[] array = {0, 1, -1, 0} 
int[] tmp = {0, 1, 0, 0} 

通過施加0求和子陣列由以下指標界定上述相同的算法（包括）：

[0] [0-2] [0-3] [1-2] [1-3] [3]

雖然多個條目的存在具有相同的值可能會影響取決於實現算法的複雜性，我相信，通過使用TMP倒排索引（映射值，它出現的指標），我們可以保持O（n）的運行時間。

Answer 2

這與Gevorg提出的方法是一樣的，但我已經使用散列圖進行快速查找。儘管O（n）複雜度使用了額外的空間。

private static void subArraySumsZero() 
{ 
    int [] seed = new int[] {1,2,3,4,-9,6,7,-8,1,9}; 
    int currSum = 0; 
    HashMap<Integer, Integer> sumMap = new HashMap<Integer, Integer>(); 
    for(int i = 0 ; i < seed.length ; i ++) 
    { 
     currSum += seed[i]; 
     if(currSum == 0) 
     { 
      System.out.println("subset : { 0 - " + i + " }"); 
     } 
     else if(sumMap.get(currSum) != null) 
     { 
      System.out.println("subset : { " 
           + (sumMap.get(currSum) + 1) 
           + " - " + i + " }"); 
      sumMap.put(currSum, i); 
     } 
     else 
      sumMap.put(currSum, i); 
    } 
    System.out.println("HASH MAP HAS: " + sumMap); 
} 

輸出產生具有元件（從零開始）的索引：

subset : { 1 - 4 } 
subset : { 3 - 7 } 
subset : { 6 - 8 } 

Answer 3

一個數組包含正數和負數。找到子陣列具有最大總和

public static int findMaxSubArray(int[] array) 
{ 
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0; 
    while(i<array.length) 
    { 
     if(cumulativeSum+array[i]<0) 
     { 
      cumulativeSum=0; 
      savepoint=start; 
      start=i+1; 
     } 
     else 
      cumulativeSum=cumulativeSum+array[i]; 
     if(cumulativeSum>max) 
     { 
       max=cumulativeSum; 
       savepoint=start; 
       end=i; 
     } 
     i++; 
    } 

    System.out.println("Max : "+max+" Start indices : "+savepoint+" end indices : "+end); 
    return max; 

} 

Answer 4

這裏是我的實現，這是顯而易見的方法因此它可能是局部優化，但至少它的清晰。如果我錯了，請糾正我。

從數組的每個索引開始，計算並比較各個總和（tempsum）與所需總和（在這種情況下，sum = 0）。由於整數有符號，我們必須計算每種可能的組合。

如果您不需要完整的子數組列表，您可以隨時在內部循環中添加條件以打破它。 （假設你只是想知道這樣的子數組是否存在，只需在tempsum = sum時返回true）。

public static string[] SubArraySumList(int[] array, int sum) 
{ 
    int tempsum; 
    List<string> list = new List<string>(); 
    for (int i = 0; i < array.Length; i++) 
    { 
     tempsum = 0; 
     for (int j = i; j < array.Length; j++) 
     { 
      tempsum += array[j]; 
      if (tempsum == sum) 
      { 
       list.Add(String.Format("[{0}-{1}]", i, j)); 
      } 
     } 
    } 
    return list.ToArray(); 
} 

調用函數：

int[] array = SubArraySumList(new int { 0, -1, 1, 0 }, 0)); 

打印輸出數組的內容：

[0-0], [0-2], [0-3], [1-2], [1-3], [3-3] 

Answer 5

希望這會有所幫助。

int v[DIM] = {2, -3, 1, 2, 3, 1, 4, -6, 7, -5, -1}; 
int i,j,sum=0,counter=0; 

    for (i=0; i<DIM; i++) { 
     sum = v[i]; 
     counter=0; 
     for (j=i+1; j<DIM;j++) { 
      sum += v[j]; 
      counter++; 
      if (sum == 0) { 
       printf("Sub-array starting from index %d, length %d.\n",(j-counter),counter +1); 
      } 
     } 
    } 

Answer 6

1. Given A[i] 
    A[i] | 2 | 1 | -1 | 0 | 2 | -1 | -1 
-------+---|----|--------|---|----|--- 
sum[i] | 2 | 3 | 2 | 2 | 4 | 3 | 2 

2. sum[i] = A[0] + A[1] + ...+ A[i] 
3. build a map<Integer, Set> 
4. loop through array sum, and lookup map to get the set and generate set, and push <sum[i], i> into map. 

Complexity O(n) 

Answer 7

下面的代碼可以找出每一個可能的子陣列具有總和爲給定數量，和（當然），它可以找出那種最短和最長的子陣列。

public static void findGivenSumSubarray(int arr[], int givenSum) { 
    int sum = 0; 
    int sStart = 0, sEnd = Integer.MAX_VALUE - 1; // Start & end position of the shortest sub-array 
    int lStart = Integer.MAX_VALUE - 1, lEnd = 0; // Start & end position of the longest sub-array 

    HashMap<Integer, ArrayList<Integer>> sums = new HashMap<>(); 
    ArrayList<Integer> indices = new ArrayList<>(); 

    indices.add(-1); 
    sums.put(0, indices); 

    for (int i = 0; i < arr.length; i++) { 
     sum += arr[i]; 
     indices = sums.get(sum - givenSum); 
     if(indices != null) { 
      for(int index : indices) { 
       System.out.println("From #" + (index + 1) + " to #" + i); 
      } 
      if(i - indices.get(indices.size() - 1) < (sEnd - sStart + 1)) { 
       sStart = indices.get(indices.size() - 1) + 1; 
       sEnd = i; 
      } 
      if(i - indices.get(0) > (lEnd - lStart + 1)) { 
       lStart = indices.get(0) + 1; 
       lEnd = i; 
      } 
     } 
     indices = sums.get(sum); 
     if(indices == null) { 
      indices = new ArrayList<>(); 
     } 
     indices.add(i); 
     sums.put(sum, indices); 
    } 

    System.out.println("Shortest sub-arry: Length = " + (sEnd - sStart + 1) + ", [" + sStart + " - " + sEnd + "]"); 
    System.out.println("Longest sub-arry: Length = " + (lEnd - lStart + 1) + ", [" + lStart + " - " + lEnd + "]"); 
} 

Answer 8

以下解決方案找到具有給定總和k的最大長度子數組而不使用動態編程，但使用簡單的遞歸。這裏I_S是開始索引和I_E爲總和的當前值結束索引

##Input the array and sum to be found(0 in your case) 
a = map(int,raw_input().split()) 
k = int(raw_input()) 

##initialize total sum=0 
totalsum=0 

##Recursive function to find max len 0 
def findMaxLen(sumL,i_s,i_e): 
    if i_s<len(a)-1 and i_e>0: 
     if sumL==k: 
      print i_s, i_e 
      return (i_s,i_e) 
     else: 
      x = findMaxLen(sumL-a[i_s],i_s+1,i_e) 
      y = findMaxLen(sumL-a[i_e],i_s,i_e-1) 
      if x[1]-x[0]>y[1]-y[0]: 
       return x 
      else: 
       return y 
    else: 
     ##Result not there 
     return (-1,-1) 


## find total sum 
for i in range(len(a)): 
    totalsum += a[i] 

##if totalsum==0, max array is array itself 
if totalsum == k: 
    print "seq found at",0,len(a)-1 

##else use recursion 
else: 
    print findMaxLen(totalsum,0,len(a)-1) 

時間複雜度是O（n）和空間複雜度是O（n），由於遞歸存儲器堆疊

Answer 9

下面是一個O(n)在java

想法實現是通過給定的數組來迭代和爲每個元件arr[i]，計算總和的元件形成0到i，存儲每個sum在HashMap。

• 如果元素是0，它considerd作爲一個ZeroSum子陣列。

• 如果sum成爲0，然後有一個ZeroSum子陣列，從0到i。

• 如果當前總和已經HashMap見過的，那麼有一個ZeroSum子陣列，從該點到i。

代碼：

import java.util.*; 
import java.lang.*; 

class Rextester 
{ 
    private static final int[] EMPTY = {}; 
    // Returns int[] if arr[] has a subarray with sero sum 
    static int[] findZeroSumSubarray(int arr[]) 
    { 
     if (arr.length == 0) return EMPTY; 
     // Creates an empty hashMap hM 
     HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); 
     // Initialize sum of elements 
     int sum = 0;   
     for (int i = 0; i < arr.length; i++) 
     { 
      sum += arr[i]; 
      if (arr[i] == 0) //Current element is 0 
      { 
       return new int[]{0}; 
      } 
      else if (sum == 0) // sum of elements from 0 to i is 0 
      { 
       return Arrays.copyOfRange(arr, 0, i+1); 
      } 
      else if (hM.get(sum) != null) // sum is already present in hash map 
      { 
       return Arrays.copyOfRange(arr, hM.get(sum)+1, i+1); 
      } 
      else 
      { 
       // Add sum to hash map 
       hM.put(sum, i); 
      } 
     }  
     // We reach here only when there is no subarray with 0 sum 
     return null; 
    }   

    public static void main(String arg[]) 
    { 
     //int arr[] = {}; 
     int arr[] = { 2, -3, 1, 4, 6}; //Case left 
     //int arr[] = { 0, 2, -3, 1, 4, 6}; //Case 0 
     //int arr[] = { 4, 2, -3, 1, 4}; // Case middle 
     int result[] = findZeroSumSubarray(arr); 
     if (result == EMPTY){ 
      System.out.println("An empty array is ZeroSum, LOL"); 
     } 
     else if (result != null){ 
      System.out.println("Found a subarray with 0 sum :"); 
      for (int i: result) System.out.println(i); 
     } 
     else 
      System.out.println("No Subarray with 0 sum");    
    }   
} 

請看這裏的實驗：http://rextester.com/PAKT41271

Answer 10

希望這有助於你。

private static void subArrayZeroSum(int array[] , int findSum){ 
    Map<Integer,HashSet<Integer>> map = new HashMap<Integer,HashSet<Integer>>(); 
    int sum = 0; 
    for(int index = 0 ; index < array.length ; index ++){ 
     sum +=array[index]; 
     if(array[index] == findSum){ 
      System.out.println(" ["+index+"]"); 
     } 
     if(sum == findSum && index > 0){ 
      System.out.println(" [ 0 , "+index+" ]"); 
     } 
     if(map.containsKey(sum)){ 
      HashSet<Integer> set = map.get(sum); 
      if(set == null) 
       set = new HashSet<Integer>(); 

      set.add(index); 
      map.put(sum, set); 

      for(int val : set){ 

       if(val + 1 != index && (val + 1) < index){ 
        System.out.println("["+(val + 1) +","+index+" ]"); 
       } 
      } 

     }else{ 
      HashSet<Integer> set = map.get(sum); 
       if(set == null) 
        set = new HashSet<Integer>(); 
       set.add(index); 
      map.put(sum, set); 
     } 
    }   
}