如何找到具有O（n）時間複雜度的和k的所有子陣列？

Question

我可以搜索與下面的代碼之和k中的子陣列：

public static void subarraySum(int[] arr, int sum) { 

    int start=0; 
    int currSum=arr[0]; 

    for(int i = 1;i<=arr.length;i++) { 
     while(currSum>sum) { 
      currSum-=arr[start]; 
      start++; 
     } 
     if(currSum==sum) { 
      System.out.println(start + " " + (i-1) + " index"); 
      start=i; 
      currSum=0; 
     } 
     if(i<arr.length) { 
      currSum +=arr[i]; 
     } 

    } 

這將爲陣列工作像{15,2,4,8,9,5,10,23}。這個輸出將是2個子陣列{2,4,9,8}和{23}。

但是，對於像{1,5,2,5,1,3}這樣的數組，這隻會給我輸出爲1個子數組，但是有2個子數組和7是{5,2}和{2 ，5}。 關於如何在第二個數組中給出正確答案的上述代碼的任何建議？

Answer 1

這個算法並不複雜，我會解釋一下這個想法，然後讓實現給你試試。

你需要有兩個索引i，j，使它們都從第一個元素開始，現在將它們之間的子數組（兩者都初始化，因爲它們都在同一個地方沒有子數組），並執行以下測試。

• ，如果它的總和等於你的目標，然後添加當前的子陣列

• 如果總和小於你的目標邁進J確定的權利包括一個 多個元素，做了測試再次

• 如果總和大於您的目標，請移至右側以從子數組中移除 第一個元素並再次執行測試。

你會爲一切的總和等於toyour目標子陣

請注意這個解決方案最終只適用於正數

Answer 2

是的，我是太慢了。當我解決這個問題來給出一個代碼時，我們有一個corrent algorytm答案。 +1它從我和我的任意代碼爲溶液（我曾在採訪中許多耳前這個問題）：

public static List<int[]> subarraySum(int[] arr, int sum) { 
    List<int[]> res = new ArrayList<>(); 
    int[] tmp; 
    int start = 0; // inclusive 
    int end = 0; // exclusive 
    int currSum = 0; 

    do { 
     if (end == arr.length && currSum < sum) 
      break; 
     if (currSum > sum) 
      currSum -= arr[start++]; 
     else if (currSum < sum) 
      currSum += arr[end++]; 
     else if (currSum == sum) { 
      res.add(tmp = new int[end - start]); 
      System.arraycopy(arr, start, tmp, 0, tmp.length); 
      currSum -= arr[start]; 
      start++; 
     } 
    } while (start <= arr.length && end <= arr.length); 

    return res; 
} 

它看起來是正確的，但我只在一對夫婦的情況下測試了這個解決方案。