C++删除一组列表中的重复项

Question

我正在尝试删除 this question 中返回列表中的重复项

给定候选数字 (C) 和目标数字 (T) 的集合，找到 C 中候选数字总和为 T 的所有唯一组合。

C 中的每个数字只能在组合中使用一次。

注意:

1. 所有数字(包括目标)都是正整数。

2. 组合 (a1, a2, … , ak) 中的元素必须按非降序排列。 (即 a1 ≤ a2 ≤ … ≤ ak)。

3. 解决方案集不得包含重复的组合。

例如，给定候选集 10,1,2,7,6,1,5 和目标 8， 解决方案集是:

[1, 7] 
[1, 2, 5] 
[2, 6] 
[1, 1, 6] 

我的问题是如何有效地去除重复？ 以下是我的代码:

public class Solution {
    public static void main(String[] args) {
        int[] input = { 10, 1, 2, 7, 6, 1, 5 };
        // int[] input = { 2, 1, 1, 4, 4, 2 };
        System.out.println(combinationSum2(input, 8));
    }

    private static class Entry {
        List<Integer> list;
        int target;
        int index; // the previous index

        public Entry(int target) {
            list = new LinkedList<Integer>();
            this.target = target;
        }

        public int add(int num, int index) {
            this.list.add(num);
            this.index = index;
            this.target -= num;
            return target;
        }

        public Entry copy() {
            Entry copy = new Entry(this.target);
            copy.list = new ArrayList<>();
            copy.list.addAll(list);
            copy.target = target;
            copy.index = index;
            return copy;
        }

    }

    public static List<List<Integer>> combinationSum2(int[] input, int target) {
        List<List<Integer>> ret = new LinkedList<List<Integer>>();

        if (null == input || input.length <= 0)
            return ret;

        Arrays.sort(input);

        int N = input.length;
        Queue<Entry> pool = new LinkedList<Entry>();
        for (int i = 0; i < N; i++) {
            if (input[i] <= target) {
                Entry entry = new Entry(target);
                entry.add(input[i], i);
                pool.add(entry);
            }
        }

        while (!pool.isEmpty()) {
            Entry cur = pool.poll();
            if (cur.target == 0) {
                ret.add(cur.list);
            } else if (cur.target > 0) {
                for (int i = cur.index + 1; i < N; i++) {
                    if (cur.target - input[i] >= 0) {
                        Entry copy = cur.copy();
                        copy.add(input[i], i);
                        pool.offer(copy);
                    } else {
                        break;
                    }
                }
            }
        }

        return ret;
    }
}

我的第一个想法是对返回列表中的列表进行排序，将它们逐一比较以去除重复。但是有没有更快的方法呢？或任何建议？

Answer 1

我的建议是使用 HashSet 来防止添加任何现有条目。 要做的第一件事是重写 Entry 类的 equals 和 hashCode 函数。 ( more material )

private static class Entry {
    List<Integer> list;
    int target;
    int index;
    int hash; // <---- add this

    public Entry(int target) {
        list = new LinkedList<Integer>();
        this.target = target;
        hash = target;
    }

    public int add(int num, int index) {
        this.list.add(num);
        this.index = index;
        this.target -= num;
        hash = hash * 17 + num;
        return target;
    }

    public Entry copy() {
        Entry copy = new Entry(this.target);
        copy.list = new ArrayList<>();
        copy.list.addAll(list);
        copy.target = target;
        copy.index = index;
        copy.hash = hash;
        return copy;
    }

    @Override
    public boolean equals(Object obj) {
        Entry e = (Entry) obj;
        if ((this.target != e.target) || (this.list.size() != e.list.size())) {
            return false;
        }
        for (int i = 0; i < this.list.size(); i++) {
            if (!this.list.get(i).equals(e.list.get(i)))
                return false;
        }
        return true;
    }

    @Override
    public int hashCode() {
        return hash;
    }
}

下一步是使用哈希集来过滤结果。

Set<Entry> nodup = new HashSet<Entry>();

while (!pool.isEmpty()) {
    Entry cur = pool.poll();
    if (cur.target == 0) {
        nodup.add(cur);
    } else if (cur.target > 0) {
        // ... your code
    }
}

for (Entry entry : nodup) {
    ret.add(entry.list);
}