java - 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) 将返回列表 [0, 2]，因为列表 l 包含子-list [4, 3, 5] 从索引 0 开始，到索引 2 结束，其中 4 + 3 + 5 = 12，即使列表中稍后出现较短的序列 (5 + 7)。另一方面，给定列表 l 为 [1, 2, 3, 4] 且键 t 为 15，函数 answer(l, t) 将返回 [-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;
}