每日算法题——两数之和
许久不见，终于开始在公司上班了，有一点不好的就是一整天都要戴着口罩，闷得慌，不知道大伙儿有没有这种感觉。
又到了每日算法题了，今天继续带来一道简单的题，有兴趣的可以跟着LZ一起刷哈！
题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例：
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
这道题乍一看好像没有什么迹可寻，而且题目也没有规定什么时间/空间复杂度，所以我们可以自由发挥，算法里面有一种叫做暴力解题的方法，刚好可以用在这里试试。
解题思路
最简单粗暴的办法就是两个for循环套一起，查一下 i + j 的和是不是为 target，但是这种N^2时间复杂度就有点高了，当我们很容易的找到时间复杂度为N^2的解题办法时，我们就需要考虑一下怎么去优化成N的时间复杂度。我们来思考一下，上述说的暴力法，在第一遍遍历数组元素之后还需要再挨个遍历数组的元素来找到另一个数，也就是说我们每找一个数都花了N的时间，那么有没有什么办法能让我们再找第一遍的时候就顺便把第二个数字也找出来，当然是有的了，我们都知道，HashMap 是一个有着映射关系的集合，而且是两两对应的，我们在遍历数组的时候把当前元素和它的下标存到集合中，再判断集合中是不是有目标值与当前元素的差值，如果有的话就说明我们找到了这两个元素。很好理解哈，暴力法是重复遍历了很多次，而我们使用哈希来保存遍历的过程，这样可以减少重复遍历的次数。
题解
private int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i])) {
return new int[]{i, map.get(target - nums[i])};
} else {
map.put(nums[i], i);
}
}
return null;
}
private int[] twoSum(int[] nums, int target) {
List<Integer> list = new ArrayList<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
if (list.contains(target - nums[i])) {
result[0] = nums[i];
result[1] = target - nums[i];
break;
} else {
list.add(nums[i]);
}
}
int[] index = new int[]{-1, -1};
for (int i = 0; i < nums.length; i++) {
if (result[0] == nums[i] || result[0] == target - nums[i]) {
if (index[1] != -1) {
break;
}
if (index[0] == -1) {
index[0] = i;
} else {
index[1] = i;
}
}
}
return index;
}
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-03-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录