时间戳

首页 > 解决方案 > 如何使用哈希表来解决 leetcode 中的“二和”问题？

java - 如何使用哈希表来解决 leetcode 中的“二和”问题？

问题描述

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
        int complement = target - nums[i];
        if (map.containsKey(complement) && map.get(complement) != i) {
            return new int[]{i, map.get(complement)};
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

我正在尝试使用 Hashtable 方法在 leetcode 中进行“两个和”。但是，当我运行上面的代码时，它最终会引发异常。当我将行放在map.put(nums[i], i)for 循环的末尾，并删除“if”子句中的第二个条件时

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) {
            return new int[]{i, map.get(complement)};
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}

此代码运行正确。这两个版本的代码有什么区别？

标签： javahashtablesemantics

解决方案

第一个代码无法处理目标由两个相等的元素组成的测试用例。考虑这个测试用例：

nums=[1,2,2] target=4.

第二个代码是正确的。虽然第一个不是：

在处理最后一个元素（2）时，首先将地图中现有的 <2,1> 条目替换为 <2,2> map.put(nums[i], i);，然后 if 子句将是 fasle(map.get(complement) 将等于 i ，即 2)，这会使代码抛出异常。

为了避免代码在某些测试用例中失败，在编码之前，我们应该首先考虑不同的测试用例，这称为TDD（Test Driven Development）。多练习会给你一些关于如何计算我们所有可能的测试用例的想法。

推荐阅读