两数之和

一、问题描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那两个整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。

你可以按任意顺序返回答案。

示例一

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例二

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例三

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

• 2 <= nums.length <= 104
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• 只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

二、解决方案

1、暴力破解法

通过两个嵌套循环，找出数组中两数之和为 target 的两个元素的下标。

时间复杂度为 O(n²)

2、使用哈希表

可以采取空间换取时间的方式，将数组中的值及下标放到 HashMap 中，由于哈希表可以支持其作出近似于恒定时间的快速查找（键通过哈希运算之后会放到数组中相同下标的位置，查找时对键进行哈希运算得到结果，之后到数组中取相应位置的值即可），之后通过遍历数组从哈希表中查即可加快速度。

对于 HashMap 来说，假如哈希函数将元素适当地分散到各个桶中，则基本操作 get 和 put 提供恒定时间的性能。未发生哈希冲突的情况下，时间复杂度为 O(1)，即常数时间；在发生哈希冲突时，哈希桶中的数据结构将转换为链表或红黑树，这种情况下，基础操作 get 和 put 的时间复杂度最坏可以达到 O(n)，其中 n 为桶中元素数量。

使用 HashMap 来处理此问题，有两种做法：

• 第一种做法需要两次遍历。第一次遍历遍历将数组中的所有元素放到 HashMap 中，然后进行第二次遍历，在 HashMap 中寻找与遍历的当前元素值之和为目标值的元素。
• 第二种做法只需要一次遍历。在遍历过程中，向 HashMap 中存放元素，同时判断 HashMap 中是否存在与当前遍历值相加等于目标值的元素。

3、一遍哈希表

这种做法可以通过一次遍历实现，在遍历的过程中添加元素到HashMap中，同时判断HashMap中是否存在于当前遍历值相加等于目标值的数。

与两遍遍历不同的是，当遍历到满足条件的元素时，该元素应该放到结果数组的后一位。因为先发现结果数组中的第一个数时，第二个数还没有被添加到HashMap中。

三、Java 代码实现

1、嵌套循环

/**
 * <p>通过两个嵌套循环，找出数组中两数之和为 target 的两个元素的下标
 *
 * @param nums   给定的整数数组
 * @param target 目标值
 * @return int[]    数组 nums 中和为 target 的两个值的下标数组
 */
public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}

2、使用 HashMap 和两次遍历

/**
 * <p>两次循环遍历
 * <p>第一次循环将数组中的元素及下标添加到 HashMap 中
 * <p>第二次遍历数组，从 HashMap 中找出与当前遍历元素相加等于 target 的元素
 *
 * @param nums   给定的整数数组
 * @param target 目标值
 * @return int[]    数组 nums 中和为 target 的两个值的下标数组
 */
public int[] twoSumHash(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        if (map.containsKey(temp) && map.get(temp) != i) {
            return new int[]{i, map.get(temp)};
        }
    }
    return null;
}

使用 HashMap 时需要注意，如果源数组中有两个相同的元素，目标值为这两个元素相加，这种为特殊情况。比如，源数组为 {1, 3, 2, 3}，目标值为 6，为两个 3 相加。因为两个 3 的哈希码相同，所以遍历一遍数组，在 HashMap 中后一个 3 的索引会覆盖掉前一个 3 的索引，遍历结束时，HashMap 中的结果如下：{1:0, 2:2, 3:3}。此时，遍历第二遍数组，在遍历到第一个 3 时，即可找到和为目标值的两个元素，在返回数组中，第一个元素为当前元素的索引位置，第二个元素为从 HashMap 中获取到的元素的索引位置。

3、使用 HashMap 和一次遍历

/**
 * <p>一次循环遍历
 * <p>在循环过程中在不断向 HashMap 中添加数组元素的同时在 HashMap 中寻找与当前遍历元素相加等于 target 的元素
 * <p>与两次遍历哈希表不同，当遍历到满足条件的元素时，该元素应该放到结果数组的后一位。
 *
 * @param nums   给定的整数数组
 * @param target 目标值
 * @return int[]    数组 nums 中和为 target 的两个值的下标数组
 */
public int[] twoSumOnceHash(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        int temp = target - nums[i];
        if (map.containsKey(temp) && map.get(temp) != i) {
            return new int[]{map.get(temp), i};
        }
        map.put(nums[i], i);
    }
    return null;
}

使用 HashMap 并且只需要一次遍历的情况，不会遇到相同哈希码的值在 HashMap 中覆盖的问题，因为遍历到第二个需要的数值之后，可以从 HashMap 中获取到第一个需要的数值，之后就返回并终止方法了，并不会将两个需要的且值相等的数值都放到 HashMap 中。

需要注意的是，正在返回数组时，两边遍历会先获取第一个元素，之后在 HashMap 中获取第二个元素。而一遍遍历会获取到第二个元素，之后在 HashMap 这种获取第一个元素。所以在返回的索引数组中，两个元素的位置应该反过来。如下所示：

// 两次遍历
return new int[]{i, map.get(temp)};
// 一次遍历
return new int[]{map.get(temp), i};

四、测试

1、通过性测试

@Slf4j
class SolutionTest2 {

    @Data
    @Accessors(chain = true)
    @NoArgsConstructor
    @AllArgsConstructor
    static class InputOutput {

        private int[] source;

        private int target;

        private int[] result;
    }

    private final List<InputOutput> inputOutputList = List.of(
            new InputOutput(new int[]{3, 2, 4}, 6, new int[]{1, 2}),
            new InputOutput(new int[]{1, 3, 7, 5, 11, 4, 8}, 7, new int[]{1, 5}),
            new InputOutput(new int[]{1, 3, 2, 11, 8, 4, 6}, 8, new int[]{2, 6}),
            new InputOutput(new int[]{3, 3}, 6, new int[]{0, 1}),
            new InputOutput(new int[]{1, 3, 3}, 6, new int[]{1, 2}),
            new InputOutput(new int[]{1, 3, 2, 7, 3}, 6, new int[]{1, 4})
    );

    private final Solution solution = new Solution();

    @Test
    void twoSum() {
        for (InputOutput inputOutput : inputOutputList) {
            Assertions.assertArrayEquals(inputOutput.result, solution.twoSum(inputOutput.getSource(), inputOutput.getTarget()));
        }
    }

    @Test
    void twoSumHash() {
        for (int i = 0; i < inputOutputList.size(); i++) {
            InputOutput inputOutput = inputOutputList.get(i);
            Assertions.assertArrayEquals(inputOutput.result, solution.twoSumHash(inputOutput.getSource(), inputOutput.getTarget()));
        }
    }

    @Test
    void twoSumOnceHash() {
        for (int i = 0; i < inputOutputList.size(); i++) {
            InputOutput inputOutput = inputOutputList.get(i);
            log.info("第 {} 条测试数据，input: {}, target: {}, output: {}", i + 1, inputOutput.source, inputOutput.target, inputOutput.result);
            Assertions.assertArrayEquals(inputOutput.result, solution.twoSumOnceHash(inputOutput.getSource(), inputOutput.getTarget()));
        }
    }

}

输出结果：

[16:02:08.992][INFO ] cn.z2huo.leetcode.problem.NO_0001.SolutionTest2:67 twoSumOnceHash - 第 1 条测试数据，input: [3, 2, 4], target: 6, output: [1, 2]
[16:02:08.995][INFO ] cn.z2huo.leetcode.problem.NO_0001.SolutionTest2:67 twoSumOnceHash - 第 2 条测试数据，input: [1, 3, 7, 5, 11, 4, 8], target: 7, output: [1, 5]
[16:02:08.995][INFO ] cn.z2huo.leetcode.problem.NO_0001.SolutionTest2:67 twoSumOnceHash - 第 3 条测试数据，input: [1, 3, 2, 11, 8, 4, 6], target: 8, output: [2, 6]
[16:02:08.995][INFO ] cn.z2huo.leetcode.problem.NO_0001.SolutionTest2:67 twoSumOnceHash - 第 4 条测试数据，input: [3, 3], target: 6, output: [0, 1]
[16:02:08.995][INFO ] cn.z2huo.leetcode.problem.NO_0001.SolutionTest2:67 twoSumOnceHash - 第 5 条测试数据，input: [1, 3, 3], target: 6, output: [1, 2]
[16:02:08.996][INFO ] cn.z2huo.leetcode.problem.NO_0001.SolutionTest2:67 twoSumOnceHash - 第 6 条测试数据，input: [1, 3, 2, 7, 3], target: 6, output: [1, 4]

2、方法耗时测试

@Slf4j
@TestMethodOrder(MethodOrderer.OrderAnnotation.class)
public class SpeedTest {

    private static SolutionTest2.InputOutput executionInputOutput;

    private final Solution solution = new Solution();

    @Test
    @Disabled
    public void init() {
        initExecutionInputOutput();
    }

    @BeforeAll
    public static void initExecutionInputOutput() {
        int size = 1_000_000;
        int[] source = new int[size];
        for (int i = 0; i < size; i++) {
            source[i] = RandomUtil.randomInt(1, size + 1);
        }

        int index = RandomUtil.randomInt(0, size - 1);
        int index2 = RandomUtil.randomInt(index + 1, size);

        source[index] = RandomUtil.randomInt(size + 1, 2 * size);
        source[index2] = RandomUtil.randomInt(size + 1, 2 * size);

        int target = source[index] + source[index2];

        executionInputOutput = new SolutionTest2.InputOutput(source, target, new int[]{index, index2});

        log.info("待验证数据信息如下：");
        log.info("两数之和为 {}，和为 {} 的两个整数的数组下标为 {}", executionInputOutput.getTarget(), executionInputOutput.getTarget(),
                executionInputOutput.getResult());
        log.info("数组下标为 {} 的整数值为 {}，数组下标为 {} 的整数值为 {}",
                executionInputOutput.getResult()[0], executionInputOutput.getSource()[executionInputOutput.getResult()[0]],
                executionInputOutput.getResult()[1], executionInputOutput.getSource()[executionInputOutput.getResult()[1]]);
        log.info("");
        log.info("待查询数组大小：{} bytes", RamUsageEstimator.shallowSizeOf(source));
    }

    @Test
    @Order(1)
    void twoSum() {
        long start, end;
        int[] resultArray;

        start = System.currentTimeMillis();
        resultArray = solution.twoSum(executionInputOutput.getSource(), executionInputOutput.getTarget());
        end = System.currentTimeMillis();
        log.info("twoSum 执行时间：{} ms", end - start);
        Assertions.assertArrayEquals(executionInputOutput.getResult(), resultArray);
    }

    @Test
    @Order(2)
    void twoSumHash() {
        long start, end;
        int[] resultArray;

        start = System.currentTimeMillis();
        resultArray = solution.twoSumHash(executionInputOutput.getSource(), executionInputOutput.getTarget());
        end = System.currentTimeMillis();
        log.info("twoSumHash 执行时间：{} ms", end - start);
        Assertions.assertArrayEquals(executionInputOutput.getResult(), resultArray);
    }

    @Test
    @Order(3)
    void twoSumOnceHash() {
        long start, end;
        int[] resultArray;

        start = System.currentTimeMillis();
        resultArray = solution.twoSumOnceHash(executionInputOutput.getSource(), executionInputOutput.getTarget());
        end = System.currentTimeMillis();
        log.info("twoSumOnceHash 执行时间：{} ms", end - start);
        Assertions.assertArrayEquals(executionInputOutput.getResult(), resultArray);
    }

}

输出结果如下：

[17:23:01.159][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:45 initExecutionInputOutput - 待验证数据信息如下：
[17:23:01.169][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:46 initExecutionInputOutput - 两数之和为 3492882，和为 3492882 的两个整数的数组下标为 [391149, 803912]
[17:23:01.170][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:48 initExecutionInputOutput - 数组下标为 391149 的整数值为 1692734，数组下标为 803912 的整数值为 1800148
[17:23:01.170][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:51 initExecutionInputOutput - 
[17:23:01.178][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:52 initExecutionInputOutput - 待查询数组大小：4000016 bytes
[17:23:58.462][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:64 twoSum - twoSum 执行时间：57263 ms
[17:23:58.597][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:77 twoSumHash - twoSumHash 执行时间：127 ms
[17:23:58.787][INFO ] cn.z2huo.leetcode.problem.NO_0001.SpeedTest:90 twoSumOnceHash - twoSumOnceHash 执行时间：188 ms

暴力破解法，耗时与结果中第一个元素中所处的位置有关，第一个元素位置越靠数组后部，循环次数越多，耗时越多。

两个使用 HashMap 的方法，耗时短很多很多。

相关链接

OB links

[[HashMap]]

[[hashCode 方法和 equals 方法]]

OB tags

#LeetCode #算法