克服 HashMap 中 fail-fast 迭代器的方法

Question

在竞争性编程中，我正在解决一个给定的问题 - 给定一个非负整数数组 nums 和一个目标总和 S，我们必须找出我们的方法数可以从给定数字的总和中获得目标总和（其中每个 nums[i] 可以作为 nums[i] 或 -nums[i].

虽然我遇到了一些主要依赖数组直接访问表的解决方案（规定数字之和不能超过1000），但我尝试使用HashMap来减少所需的space。我的代码如下-

    public int findTargetSumWays(int[] nums, int S) {
        Map<Integer, Integer> dp = new HashMap();
        dp.put(nums[0], 1);
        dp.put(-nums[0], dp.getOrDefault(-nums[0], 0) + 1);
        
        for (int i=1; i<nums.length; i++) {
            for (Integer sum : dp.keySet()) {
                dp.put(sum+nums[i], dp.getOrDefault(sum+nums[i], 0) + 1);
                dp.put(sum-nums[i], dp.getOrDefault(sum-nums[i], 0) + 1);
            }
        }
        return dp.get(S);
    }

但是我在运行代码上遇到了 ConcurrentModificationException。我试着找到这个问题。尽管我对迭代中的集合视图在结构上无法进行修改有了一些概念性的理解，但我无法弄清楚如何绕过它来找到解决方案。

是否无法使用HashMap（或任何动态数据结构）的解决方案？感谢任何帮助。

Answer 1

ConcurrentModificationException 的原因是您在以下循环中迭代 dp.keySet() 时修改了 dp 的键：

for (Integer sum : dp.keySet()) {
    dp.put(sum+nums[i], dp.getOrDefault(sum+nums[i], 0) + 1);
    dp.put(sum-nums[i], dp.getOrDefault(sum-nums[i], 0) + 1);
}

Answer 2

for (Integer sum : dp.keySet()) {
  dp.put(sum+nums[i], dp.getOrDefault(sum+nums[i], 0) + 1);
  // ...
}

如果 sum + nums[i] 不是映射中已有的键，这会导致映射的结构修改：也就是说，您要添加新的 key/value 对。

如所述in the Javadoc：

The iterators returned by all of this class's "collection view methods" are fail-fast: if the map is structurally modified at any time after the iterator is created, in any way except through the iterator's own remove method, the iterator will throw a ConcurrentModificationException.

（如果键已经在映射中，您只需修改与该键关联的值，这样就可以了）。

解决这个问题的最简单方法是通过将元素复制到例如列表：

for (Integer sum : new ArrayList<>(dp.keySet())) {

现在，您正在迭代列表，而不是地图的键集，因此您可以在该循环内自由修改地图的结构。

除了异常问题之外，您的 put/getOrDefault 行将更简单地写为：

// dp.put(sum+nums[i], dp.getOrDefault(sum+nums[i], 0) + 1);
// becomes
dp.merge(sum+nums[i], 1, Integer::sum);

克服 HashMap 中 fail-fast 迭代器的方法

Way to overcome fail-fast iterator in HashMap

java

collections

exception

data-structures