哈希

两数之和

简单#1Java时间 O(n)空间 O(n)

题目要做什么

给定整数数组 nums 和目标值 target,返回两个不同位置的下标,使这两个位置的数之和等于 target。假设恰好有一组答案。

题目示例输入nums = [2, 7, 11, 15], target = 9
题目示例输出[0, 1]

01 为什么这样做

把已经见过的数和下标放进哈希表。每看到一个新数,只需查询它的补数是否出现过。先查询、再存入,可以避免同一位置被使用两次。

始终成立的条件

查询时,seen 只包含当前下标之前的数。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int[] twoSum(int[] nums, int target) {3        Map<Integer, Integer> seen = new HashMap<>();4        for (int i = 0; i < nums.length; i++) {5            int need = target - nums[i];6            if (seen.containsKey(need)) {7                return new int[]{seen.get(need), i};8            }9            seen.put(nums[i], i);10        }11        throw new IllegalArgumentException("无解");12    }13}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索