标题:两数之和
出处:1. 两数之和
2 级
给定一个整数数组 nums \texttt{nums} nums 和一个整数目标值 target \texttt{target} target,请你在该数组中找出和为 target \texttt{target} target 的那两个整数,并返回它们的数组下标。
你可以假设每种输入恰好有一个答案,不能重复使用数组中同一个元素。
你可以按任意顺序返回答案。
示例 1:
输入:
nums
=
[2,7,11,15],
target
=
9
\texttt{nums = [2,7,11,15], target = 9}
nums = [2,7,11,15], target = 9
输出:
[0,1]
\texttt{[0,1]}
[0,1]
解释:因为
nums[0]
+
nums[1]
=
9
\texttt{nums[0]} + \texttt{nums[1]} = \texttt{9}
nums[0]+nums[1]=9,返回
[0,
1]
\texttt{[0, 1]}
[0, 1]。
示例 2:
输入:
nums
=
[3,2,4],
target
=
6
\texttt{nums = [3,2,4], target = 6}
nums = [3,2,4], target = 6
输出:
[1,2]
\texttt{[1,2]}
[1,2]
示例 3:
输入:
nums
=
[3,3],
target
=
6
\texttt{nums = [3,3], target = 6}
nums = [3,3], target = 6
输出:
[0,1]
\texttt{[0,1]}
[0,1]
你可以想出一个时间复杂度小于 O(n 2 ) \texttt{O(n}^\texttt{2}\texttt{)} O(n2) 的算法吗?
假设数组 nums \textit{nums} nums 的长度是 n n n,则需要找到两个下标 i i i 和 j j j,满足 0 ≤ i < j < n 0 \le i < j < n 0≤i<j<n 且 nums [ i ] + nums [ j ] = target \textit{nums}[i] + \textit{nums}[j] = \textit{target} nums[i]+nums[j]=target。
最简单的做法是使用两层循环遍历,外层循环在范围 [ 0 , n − 1 ] [0, n - 1] [0,n−1] 中遍历下标 i i i,内层循环在范围 [ i + 1 , n − 1 ] [i + 1, n - 1] [i+1,n−1] 中遍历下标 j j j,当遇到一对下标 ( i , j ) (i, j) (i,j) 满足 nums [ i ] + nums [ j ] = target \textit{nums}[i] + \textit{nums}[j] = \textit{target} nums[i]+nums[j]=target 时,返回下标 i i i 和 j j j 即可。
class Solution {
public int[] twoSum(int[] nums, int target) {
int length = nums.length;
for (int i = 0; i < length; i++) {
for (int j = i + 1; j < length; j++) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[]{-1, -1};
}
}
时间复杂度: O ( n 2 ) O(n^2) O(n2),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要使用两层循环遍历数组 nums \textit{nums} nums。
空间复杂度: O ( 1 ) O(1) O(1)。
解法一中,相同的下标被重复计算了多次,因此时间复杂度较高。如果使用哈希表存储已经遍历过的元素与下标,可以将时间复杂度降低到 O ( n ) O(n) O(n)。
哈希表的键为已经遍历过的元素,值为元素所在下标。
当遍历到下标 i i i 时,令 num = nums [ i ] \textit{num} = \textit{nums}[i] num=nums[i],如果哈希表中存在元素 target − num \textit{target} - \textit{num} target−num 作为哈希表的键,则可以根据哈希表得到元素 target − num \textit{target} - \textit{num} target−num 所在下标 prevIndex \textit{prevIndex} prevIndex,此时 ( prevIndex , i ) (\textit{prevIndex}, i) (prevIndex,i) 即为答案。由于使用哈希表查找,因此对于每个元素 num \textit{num} num 都可以在 O ( 1 ) O(1) O(1) 的时间内判断 target − num \textit{target} - \textit{num} target−num 是否在哈希表中,总时间复杂度为 O ( n ) O(n) O(n)。
由于题目要求不能重复使用数组中同一个元素,因此对于每个元素 num \textit{num} num,应该首先判断哈希表中是否存在元素 target − num \textit{target} - \textit{num} target−num,然后将 num \textit{num} num 加入哈希表。如果哈希表中存在元素 target − num \textit{target} - \textit{num} target−num,则该元素的下标一定小于当前下标,因此 target − num \textit{target} - \textit{num} target−num 所在下标与 num \textit{num} num 所在下标一定不同(即使 target − num \textit{target} - \textit{num} target−num 的值与 num \textit{num} num 的值相等,如示例 3)。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
int length = nums.length;
for (int i = 0; i < length; i++) {
int num = nums[i];
if (map.containsKey(target - num)) {
int prevIndex = map.get(target - num);
return new int[]{prevIndex, i};
}
map.put(num, i);
}
return new int[]{-1, -1};
}
}
时间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要遍历数组 nums \textit{nums} nums 一次,对于每个元素都可以在 O ( 1 ) O(1) O(1) 的时间内完成对哈希表的操作,因此总时间复杂度是 O ( n ) O(n) O(n)。
空间复杂度: O ( n ) O(n) O(n),其中 n n n 是数组 nums \textit{nums} nums 的长度。需要使用哈希表存储遍历过的数字,哈希表的元素个数不会超过 n n n。