List引用的坑

发表于

做39. combinationSum时发现的问题，第一次写的答案如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
static List<List<Integer>> ret = new ArrayList<>();
public void combinationSum(int[] candidates, int target) {
    List<Integer> oneSolve = new ArrayList<>();   //问题在这里1
    help(candidates, target, oneSolve, 0);
}
public static void help(int[] candidates, int target, List<Integer> oneSolve, int sum){
    if (sum == target){
        ret.add(oneSolve);   //和这里2
        return;
    }

    for (int i = 0; i < candidates.length; i++) {
        int temp = candidates[i];
        if (sum + temp <= target){
            oneSolve.add(temp);
            help(candidates, target, oneSolve, sum+temp);
            oneSolve.remove(oneSolve.size()-1);   //这里3
        }else
            break;
    }
}

问题

最后ret 得到的结果为空值，但通过 2 中每次也都正确添加了oneSolve 的列表

原因

当2返回时，3就会改变oneSolve，而ret 中已经添加的一个列表也随之改变，都是因为每次ret 每次都是通过引用添加的列表。当oneSolve 最后移除所以元素后，ret中每个列表也就都变为空了。

以前没发现这个问题是因为传递的不是列表这样的引用，而是String之类的字符串或者直接进行计数而不涉及add这样的添加操作。

解决

2 中 ret 通过一个临时列表进行添加，即深拷贝

1
2
3
4
5
List<Integer> temp = new ArrayList<>();
for (int i = 0; i < oneSolve.size(); i++) {
    temp.add(oneSolve.get(i));
}
ret.add(temp);

但是

上面的代码还有一个问题，最后ret 会含有重复的列表，再做一些改进，记录每次递归时当前的 i 值，下一个加入列表的值从数组的 i 位置开始找：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void help(int[] candidates, int target, List<Integer> oneSolve, int sum, int i){
    if (sum == target){
        ret.add(new ArrayList<>(oneSolve));
        return;
    }

    for (; i < candidates.length;) {
        if (sum + candidates[i] <= target){
            oneSolve.add(candidates[i]);
            help(candidates, target, oneSolve, sum+candidates[i], i);
            i++;
            oneSolve.remove(oneSolve.size()-1);
        }else
            break;
    }
}