思路分析

  1. 我刚做这道题的时候上来就想到的方法是穷举,但是穷举明眼一看就不是一个最优解,时间复杂度非常高。
  2. 经过观察后发现 Map 数据结构非常适合这道题,因为 Map 可以存储数据与下标的关系,并且获取元素的时间复杂度是O(1)。
  3. 这里面说的是找到两个和为 target 的数组下标,那是不是可以理解为 找到数组中 值为 target - nums[i] 的数值下标,而这种思路就可以想到使用 hash 表来实现。

AC代码

public int[] twoSum (int[] numbers, int target) {
        // write code here
        if (numbers == null || numbers.length < 1) {
            return new int[0];
        }
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i ++) {
            int temp = target - numbers[i];
            if (map.containsKey(temp)) {
                return new int[]{map.get(temp) + 1, i + 1};
            } else {
                map.put(numbers[i], i);
            }
        }
        return new int[0];
    }

时间复杂度:O(N),N 为数组的长度,但是寻找每一个元素的时候是O(1)的复杂度,因为使用了 hash 表的数据结构。

空间复杂度:O(N),N为数组的长度,可能会将所有数存储到 hash 表汇总

总结

这道题的难点就是在数据结构的选择上,选择正确的数据结构可以大大优化时间复杂度。
注意!!!这道题下标时从 1 开始,所以返回的下标都要 + 1,注意审题!
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。

图片说明