LeetCode 01.两数之和

LeetCode 01.两数之和

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

示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

分析

通常解法估计就是两个for循环，直到找到两个数和等于 target 的值；找到两个值的和等于目标值。

但是这种解法的时间复杂就是 O(n^2) 了，如果是面试的话，那面试官肯定会问那有没有更好的解法呢，这个时候就是决定这次面试走向的时候了????。

其实是有的，咱们先分析下两次 for 循环，有哪些缺点，其实这个数组里面的每个值的话，咱们访问了很多遍，那有没有什么办法，给它记下来呢，访问了就直接匹配呢，做到一次搞定呢。

其实接下来的讲法，有点儿像相亲，配对儿。我这个值去找我需要配对的值，发现没找到的话，那我就先在登记处登记下，到时候我的另一半来找我，就可以了，美滋滋。

解法

代码尽量写得通俗易懂，也会有些注释。

import java.util.HashMap;
import java.util.Map;
/**
* @author: wangqp
* @create: 2020-08-10 17:37
*/
public class TwoSum {
public int[] twoSum(int[] nums, int target) {
//登记的值
-> 下标索引
Map<Integer,Integer> dengji = new HashMap<>();
//没找到匹配 就登记下，让别人来找
for (int i = 0; i < nums.length; i++) {
if (dengji.containsKey(target-nums[i])){
return new int[]{i,dengji.get(target-nums[i])};
}
dengji.put(nums[i],i);
}
return null;
}
}

总结

关键是理解这个题的思路，到时候咱们碰到相近的题目意思的话，就可以不用死记硬背了。
延伸：我记得LeetCode上还有很多类似的题，比如三数之和，到时候我们就可以用两数之和的解法来处理，到时候下篇博客介绍。

最后

以上就是负责酒窝为你收集整理的面试，求数组中哪两个数的和为指定值，时间复杂度 O(n)LeetCode 01.两数之和的全部内容，希望文章能够帮你解决面试，求数组中哪两个数的和为指定值，时间复杂度 O(n)LeetCode 01.两数之和所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。