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