O（n）時間の複雑さで合計kを持つすべてのサブアレイを見つけるには？

Question

Iは、以下のコードで和kのサブアレイを検索することができ：これは、{} 15,2,4,8,9,5,10,23ような配列のために働く

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]; 
     } 

    } 

。これに対する出力は、2つのサブアレイ{2,4,9,8}と{23}になります。

しかし、{1,5,2,5,1,3}のような配列の場合、これは1つのサブアレイとして出力されますが、{5,2}と{2の合計7を持つ2つのサブアレイがあります、5}。 2番目の配列に正しい答えを与えるために上記のコードをtweekする方法に関する提案はありますか？

Answer 1

アルゴリズムは複雑ではありません、私はそのアイデアを説明し、それを試してみてください。

2つのインデックスi、jを持つ必要があります。両方の要素を最初の要素で開始し、両方の要素の間でサブ配列を取るようにします（最初は両方とも同じ場所にありません）。 。

• それの合計があなたの目標に等しい場合合計が1つの より多くの要素が含まれており、テストを行うには、右にあなたの目標移動Jよりも小さい場合、現在のサブアレイ

• を追加再び

• 合計が目標よりも大きい場合は、右に移動して サブアレイから最初の要素を削除し、テストをもう一度行います。あなたはそれらの和がゴール

  toyourの等しいすべてのサブアレイを持つことになる終わり

はい、私は遅すぎるよこのソリューションは唯一の正の数

Answer 2

のために働く何卒ご了承下さい。私はコードを与えるためにこの問題を解決していましたが、私たちは丁寧な答えを持っています。それのための+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; 
} 

それが正しい見えますが、私は唯一の例のカップルにこのソリューションをテストしています。