在迭代HashSet时移除元素

Question

假设我有一个 HashSet：

代码如下：

[1, 2, 3, 4, 5, 6]

我希望以这样一种方式迭代它，即对于给定的总和（如6），在迭代元素时，如果我发现Set中有2个元素的总和等于6，则我想移除另一个元素。例如，如果我正在迭代1，则应删除5。我尝试做如下操作：

HashSet<Integer> hs = new HashSet(arr);
int sum = 6;
for(int num : hs) {
    if(hs.contains(sum - num)) {
        hs.remove(sum - num);
    }
}

显然会抛出 java.util.ConcurrentModificationException 异常。另一种方法是使用迭代器，但它会删除当前元素，并且不会将任何其他元素作为参数。还有什么其他的选择？

更新：我知道使用额外的集合等技巧。我只想要一个非常优化的解决方案，而不会增加时间和空间复杂度，如果可能的话。

- clever_bassi

---

将sum-num添加到一个新的集合hs2中，最后执行hs.removeAll(hs2)。 - JP Moresmau

我知道那种方法。试图找到更优化的方法。此外，我想仅在for循环中删除元素，以便我甚至不会迭代该元素。 - clever_bassi

从ConcurrentHashMap创建一个Set可能会有些过度，但它可以按照你想要/需要的方式工作。 - Luiggi Mendoza

如果你的总和是6，而你有数字1和5，你如何知道是删除1还是5？ - durron597

我正在迭代哈希集。如果我先遇到1，我将只删除另一个即5。我这样做是因为最终我要打印所有总和为6的数字对。如果我不删除5，则结果为1,5和5,1。为了消除这种重复，如果已经迭代了1，我想停止迭代5。 - clever_bassi

Answer 1

保持一个记录你已经找到的数字的运行集合。

这样可以让你有一个一次性的解决方案。

从一个空的运行集合开始，遍历你的数字集合。对于你遍历的每个元素，如果它的和补数在集合中，则将其从迭代器中删除。否则，将其添加到运行集合中。

HashSet<Integer> hs = new HashSet(arr);
HashSet<Integer> running = new HashSet();
int sum = 6;
Iterator<Integer> iter = hs.iterator();
while (iter.hasNext()) {
    int num = iter.next();
    if (running.contains(sum - num)) {
        iter.remove();
    } else {
        running.add(num);
    }
}

这段代码将修改原始的HashSet，两个HashSet最终都包含相同的内容。在这种情况下，最好只使用代码末尾的running集合而不修改原始集合。这将使代码更加灵活和可重用。

- Erick Robertson

---

不，第一个数字将保留，因为它的补码不在运行集中。第二个数字将被删除，因为第一个数字在运行集中。 - Erick Robertson

当然，+1。你应该提到这个方法对原始的HashSet是具有破坏性的，并且在循环结束时两个HashSet将相同（元素已被删除）。 - durron597

我知道这个技巧，但是考虑到空间的原因，我不想使用额外的 HashSet。谢谢。 - clever_bassi

我认为你会在寻找符合所有考虑因素的解决方案时遇到问题。如果一次遍历和一个集合都是要求，那么恐怕没有解决方案。 - Erick Robertson

Answer 2

你可以使用已排序的列表来代替。首先按递增顺序排序数字。然后放置2个迭代器，一个在第一个元素，另一个在最后一个元素。然后，在每一步中，如果迭代器下的2个项的总和小于所需的数字，则应增加第一个迭代器；如果大于所需数字，则应减小第二个迭代器；如果它等于您想要的值，则选择它们并增加第一个迭代器和减少第二个迭代器。

这比集合更快！

- hasan

---

10000 年历史的解决方案 - Avi