Google 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) 将 return 列表 [0, 2] 因为列表 l 包含从索引 0 开始到索引 2 结束的子列表 [4, 3, 5]，其中 4 + 3 + 5 = 12，即使列表中后面出现了更短的序列 (5 + 7).另一方面，给定列表 l 为 [1, 2, 3, 4] 和键 t 为 15，函数 answer(l, t) 将 return [-1, -1] 因为有没有列表 l 的子列表可以总结到给定的目标值 t = 15.

Answer 1

您可能不需要数组列表。您可以对数组 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

刚刚提交了我的解决方案..它被接受了，所以我知道它被Google接受了：

（我相信这会比上面的解决方案稍微快一些，因为它会打破循环并且 return 如果目标大于数组中所有数字的总和。）

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

Google Foobar 数字站

Google Foobar Numbers Station

java

puzzle

list