java谷歌Foobar数字站

Question

我正试图解决google 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，函数answer（l，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;
}