题目描述
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值target的那两个整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
输入输出样例
示例 1：
1
2
3
| 输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
|
示例 2：
1
2
| 输入：nums = [3,2,4], target = 6
输出：[1,2]
|
示例 3：
1
2
| 输入：nums = [3,3], target = 6
输出：[0,1]
|
提示：
- 2 <= nums.length <= 104
- -109 <= nums[i] <= 109
- -109 <= target <= 109
- 只会存在一个有效答案
题解
hash法
利用unordered_map数组构造映射,遍历nums[i]时，看target-nums[i]是否存在于hash表中
时间复杂度 O(n),空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> indices;
for (int i = 0; i < nums.size(); i++) {
if (indices.find(target - nums[i]) != indices.end()) {
return {indices[target - nums[i]], i};
}
indices[nums[i]] = i;
}
return {};
}
};
|
暴力破解法
暴力破解时间复杂度O($n^{2}$),空间复杂度O(1)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
for(int i=0;i<nums.size();i++){
for(int j=i+1;j<nums.size();j++){
if(nums[i]+nums[j]==target){
ans.push_back(i);
ans.push_back(j);
return ans;
}
}
}
return ans;
}
};
|
排序+双指针法
先将数组的顺序排好O(nlogn),再利用双指针法遍历一遍O(n)得到结果
为保存下标信息另开一个数组
时间复杂度O(nlogn),空间复杂度O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans;
vector<int> temp;
temp=nums;
int n=temp.size();
sort(temp.begin(),temp.end());
int i=0,j=n-1;
while(i<j){
if(temp[i]+temp[j]>target)j--;
else if(temp[i]+temp[j]<target)i++;
else break;
}
if(i<j){
for(int k=0;k<n;k++){
if(i<n&&nums[k]==temp[i]){
ans.push_back(k);
i=n;
}
else if(j<n&&nums[k]==temp[j]){
ans.push_back(k);
j=n;
}
if(i==n&&j==n)return ans;
}
}
return ans;
}
};
|