题目描述
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
题目思路
- 思路一、两层循环，第一层循环定位第一个数字，第二层循环定位第二层数字。时间复杂度为O(n2)，效率低
- 思路二、用map来实现，时间复杂度为 O(n)，不过用到map，会多用些空间
C++
- 思路一
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
int length = nums.size();
for(int i = 0; i < length-1; i++){
for(int j = i+1; j < length; j++)
if(nums[i] + nums[j] == target){
result.push_back(i);
result.push_back(j);
break;
}
}
return result;
}
};
- 思路二
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
map<int, int> mp;
int length = nums.size();
for(int i = 0; i < length; i++){
if(mp.find(target - nums[i]) != mp.end()){
result.push_back(mp[target-nums[i]]);
result.push_back(i);
break;
}
mp[nums[i]] = i;
}
return result;
}
};
