Google Foobar Numbers Station

Question

我試圖解決谷歌foobar的挑戰，但我堅持如何改變這個使用遞歸。任何指針將是有益的

public static int[] answer(int[] l, int t) { 
    // convert the array into a list 
    List<Integer> list = new ArrayList<>(); 
    for (int i : l) { 
     list.add(i); 
    } 
    for (int i = 0; i < list.size(); i++) { 
     Integer n = list.get(i); 
     if (i >= 1) { 
      Integer nMinus1 = list.get(i - 1); 
      Integer nMinus2; 
      Integer nMinus3; 
      Integer nMinus4; 
      Integer nMinus5; 
      Integer nMinus6; 
      if (n + nMinus1 == t) { 
       // done 
       return new int[]{i - 1, i}; 
      } else if (i >= 2) { 
       nMinus2 = list.get(i - 2); 
       if (n + nMinus1 + nMinus2 == t) { 
        // done 
        return new int[]{i - 2, i}; 
       } else if (i >= 3) { 
        nMinus3 = list.get(i - 3); 
        if (n + nMinus1 + nMinus2 + nMinus3 == t) { 
         // done 
         return new int[]{i - 3, i}; 
        } else if (i >= 4) { 
         nMinus4 = list.get(i - 4); 
         if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 == t) { 
          // done 
          return new int[]{i - 4, i}; 
         } else if (i >= 5) { 
          nMinus5 = list.get(i - 5); 
          if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 + nMinus5 == t) { 
           // done 
           return new int[]{i - 5, i}; 
          } else if (i >= 6) { 
           nMinus6 = list.get(i - 6); 
           if (n + nMinus1 + nMinus2 + nMinus3 + nMinus4 + nMinus5 + nMinus6 == t) { 
            // done 
            return new int[]{i - 6, i}; 
           } 
          } 
         } 
        } 
       } 
      } 
     } 
    } 
    return new int[]{-1, -1}; 
} 

這裏是這樣的問題：

鑑於列表L爲[4，3，5，7，8]和密鑰t爲12時，功能答案（1,1- t）將返回列表[0,2]，因爲列表l包含從索引0開始到索引2結束的子列表[4,3,5]，其中4 + 3 + 5 = 12，即使那裏是稍後在列表中發生的較短序列（5 + 7）。另一方面，給定列表l爲[1,2,3,4]，關鍵字t爲15，函數answer（l，t）將返回[-1，-1]，因爲沒有子列表的列表l可以總結爲給定的目標值t = 15。

Answer 1

您可能不需要arraylist。你可以在數組l上執行雙循環。你爲什麼要遞歸？

你可以這樣做：

public static int[] answer(int[] l, int t) { 
    int[] rets = {-1, -1}; 
    int sum=0; 
    for (int i=0; i<l.length; i++) { 
     sum=0; 
     for (int j=i; j<l.length; j++) { 
      sum+=l[j]; 
      if (sum > t) break; 
      if (sum == t) { 
       rets[0] = i; 
       rets[1] = j; 
       return rets; 
      }  
     } 
    } 
    return rets; 
} 

Answer 2

剛剛提交我的解決辦法..它被錄取了，所以我知道它是接受了谷歌：

（我相信這會比上面更快略解決方案，因爲如果目標大於數組中的所有數字的總和，它將打破循環並返回。）

public static int[] answer(int[] l, int t){ 
    int sum =0; 
    List<Integer> indexes = new ArrayList<>(); 

    for(int j=0;j<l.length;j++){ 
     sum = 0; 
     indexes.clear(); 
     for(int i=j;i<l.length;i++){ 

      sum += l[i]; 
      indexes.add(i); 

      if(sum >= t){ 
       break; 
      } 

     } 

     if(sum == t){ 
      break; 
     } 
     else if(sum > t){ 
      continue; 
     } 
     else{ 
      return new int[] {-1,-1}; 
     } 

    } 

    int[] returnArray = new int[2]; 

    if(indexes.size()>0){ 
     returnArray[0] = indexes.get(0); 
     returnArray[1] = indexes.get(indexes.size()-1); 
    } 

    return returnArray; 
}