0001. 两数之和 #
- 标签:数学
- 难度:简单
一、题目说明 #
描述:给定一个整数数组 nums
和一个整数目标值 target
。
要求:在该数组中找出和为 target
的两个整数,并输出这两个整数的下标。可以按任意顺序返回答案。
说明:
- $2 \le nums.length \le 10^4$。
- $-10^9 \le nums[i] \le 10^9$。
- $-10^9 \le target \le 10^9$。
- 只会存在一个有效答案。
示例:
- 示例 1:
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。
- 示例 2:
输入:nums = [3,2,4], target = 6
输出:[1,2]
二、解题思路 #
1. 暴力破解 #
-
首先有一点可以肯定:寻找整数数组
nums
中的某个或者某几个元素,必然需要通过下标来访问,那么,对数组进行遍历是一个必要的操作。 -
假设这个数组中有两个元素的下标分别是
i
和j
,正好满足nums[i] + nums[j] == target
,那么我就可以说,i
和j
就是要寻找的答案。 -
那么按照朴素的思维方式,如果能够将数组
nums
中所有的元素都两两求和,那么最终一定能找到结果。 -
为了找到索引
i
和j
,需要进行两层遍历:- 首先假设外层遍历的索引为
i
,它需要从索引0开始,一直遍历到数组的最后一个元素,即nums[nums.length - 1]
; - 在外层的遍历过程中,每次都能确定索引
i
的位置,然后将索引i
后面的元素依次与其相加,并判断是否等于target;
for(int i=0;i<nums.length-1;i++){ for(int j=i+1;j<nums.length;j++){ if(nums[i] + nums[j] == target){ //i和j即为所求 } } }
- 首先假设外层遍历的索引为
-
全量的代码如下:
public int[] twoSum(int[] nums, int target) { for(int i=0;i<nums.length-1;i++){ for(int j=i+1;j<nums.length;j++){ if(nums[i] + nums[j] == target){ return new int[]{i,j}; } } } return null; }
当然,这属于一种暴力破解的方式。其核心逻辑在于,对数组中的元素进行数学逻辑上的组合,以穷尽遍历的方式找到符合要求的数据。
其中,用到的变量只有固定的
i
和j
,所以空间复杂度为:$O(1)$。由于采用的是循环嵌套循环的方式,所以时间复杂度为:$O(n^2)$。
2. 边缓存,边遍历 #
对于上面的暴力破解而言,由于是for
循环嵌套for
循环的方式,故而时间复杂度不太理想。通过观察其流程可以发现,数组nums
中有很多元素,被反复访问了多次,如果将已访问的元素,以集合的形式存储起来,那么只需要从这个集合中去找就可以了,从而避免了元素被重复访问的问题。
确定了这一点之后,下一步就需要考虑,用哪一种集合来存储已经访问过的元素。由题意可知,我们需要找到两个元素,这两个元素之和等于目标值,然后将这两个元素的下标返回。所以,这个集合需要存储元素值,也需要存储该元素对应的数组下标,即map
。
public int[] twoSum(int[] nums, int target){
//key是数组的元素,value是数组索引下标
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;
}