思路分析
- 我刚做这道题的时候上来就想到的方法是穷举,但是穷举明眼一看就不是一个最优解,时间复杂度非常高。
- 经过观察后发现 Map 数据结构非常适合这道题,因为 Map 可以存储数据与下标的关系,并且获取元素的时间复杂度是O(1)。
- 这里面说的是找到两个和为 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,注意审题!
可以去微信搜索:【蘑菇睡不着】交个朋友~
也可以扫描下方二维码。