最長的子陣列

Question

任何人都可以爲下面的問題提出一個簡單的解決方案。

最長子陣列：查找最長連續子陣列的長度，其中在子陣列中的元素的總和小於或等於到「k」。

輸入是：array和k。

實施例：

Array = {1,2,3}, k = 3 

輸出：

說明：

子陣列：{1}，{2}，{3} ，{1,2}，{2,3}，{1,2,3}

{1,2} => max length = 2; 1 + 2 = 3（< = k）;

Answer 1

一個有效的方法是使用動態規劃，以減少求和操作的次數。例如，如果你總結（1 + 2）= 3，你不想再次求和（1 + 2 + 3）= 6，你只想求和（3 + 3）= 6（前3個已經計算並保存到散列表中）。在此解決方案中，散列映射表示從索引i到索引j的和，格式爲<i, <j, sum>>。所以你從索引i開始存儲在內部散列表中。請注意，您也可以使用二維數組而不是嵌套哈希映射結構，但對於非常大的數據，在初始化該數組時可能會遇到內存不足異常。

static int maxLength(int[] a, int k) { 
     Map<Integer, Map<Integer, Long>> map = new HashMap<Integer, Map<Integer, Long>>(); 

     int maxLength = 0; 
     for(int i = 0; i < a.length - 1; i++) { 
      Map<Integer, Long> map2 = new HashMap<Integer, Long>(); 
      map2.put(i, (long)a[i]); 
      map.put(i, map2); 
      if(a[i] == k) { 
       maxLength = 1; 
      } 
     } 

     for(int l = 2; l <= a.length; l++) { 
      long sum = 0; 
      for(int i = 0; i <= a.length - l; i++) { 
       int j = i + l - 1; 
       Map<Integer, Long> map2 = map.get(i); 
       sum = map2.get(j - 1) + a[j]; 
       map2.put(j, sum); 

       if(sum <= k) { 
        if(l > maxLength) { 
         maxLength = l; 
        } 
       } 
      } 
     } 

     return maxLength; 
    } 

Answer 2

最簡單和天真的答案是遍歷你的數組，並找到當前索引處開始的最長的子數組。

int[] a = { 1,2,3,1,1,2,3,1,3 }; 
int k = 4; 

int best_i = 0; // from index 
int best_j = 0; // to index, so best length = j - i + 1 
int best_sum = 0; 

for (int i = 0; i < a.length; i++) { // starting index from beginning to end 
    int sum = 0; 
    for (int j = i; j < a.length; j++) { // ending index from current to end 
     sum += a[j]; 
     if (sum > k) break; 
     if (j - i > best_j - best_i) { // best length found 
      best_i = i; 
      best_j = j; 
      best_sum = sum; 
     } 
    } 
} 

System.out.println("best length = " + (best_j - best_i + 1) + " (indexes " + best_i + ".." + best_j + "), sum = " + best_sum); 
// best length = 3 (indexes 3..5), sum = 4 

Answer 3

一種O（n）方法。在高電平：

有2個指針start和end，start是子陣列的開始，end是端部（排他）。一個int sum保持子陣列總和。一個int len保持子數組len。

將兩者都設置爲位置0。

1. 繼續通過移動指針end：

   while (end < arr.length && sum + arr[end] <= k) { 
       sum += arr[end]; 
       end ++; 
   } 
   if ((end - start) > len) { 
       len = (end-start); 
   } 
   

   哪個會發現你與sum < k先從最長的子陣列與start

2. 移動start

   sum -= arr[start]; 
   start++; 
   

3. 回到1日起至end通過陣列

的最後一個元素。在結束時，你會發現一些邊緣的情況下給你的最大長度（存儲在len）

休假處理（例如如果數組中存在值爲> k的元素。等）

Answer 4

這裏我只用於for循環，但我對這個解決方案的複雜性是否O（n）或O（n2）有疑問。看起來像一個for循環，但我不認爲一些操作比蠻力或兩個for循環少。

函數最大長度（A，K）{

var maxLen = 0; 
var currMaxLen = 0; 
var currSum = 0; 
var currIndex = 0; 

for(index = 0; index < a.length; index++){ 
    currSum = currSum + a[index]; 

    if(currSum <= k){ 
     currMaxLen++; 
    } else{ 
     //reset 
     index = currIndex; 
     currIndex++; 
     maxLen = Math.max(maxLen, currMaxLen); 
     currSum = 0; 
     currMaxLen = 0; 
    } 
} 
maxLen = Math.max(maxLen, currMaxLen); 
return maxLen; 

}