leetcode 练习1 two sum
whowhoha@outlook.com
问题描述
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.
Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解法1:暴力破解法: O(n^2) runtime, O(1) space – Brute force: The brute force approach is
simple. Loop through each element x and find if there is another value that
equals to target – x. As finding another value requires looping through
the rest of array, its runtime complexity
is O(n^2).
解法2:使用HashMap。把每个数都存入map中,然后再逐个遍历,查找是否有 target – nums[i]。 O(n) runtime O(n) space,
vector<int> twoSum(vector<int>&
nums, int target){
vector<int>
vec;
map<int,int> m;
for (int i = 0; i < nums.size(); i++)
{
if(m.find(target
- nums[i]) != m.end())
{
vec.push_back(m[target -
nums[i]] );
vec.push_back(i);
break;
}
m[nums[i]] = i;
}
return
vec;
}
调用:
int a[6]={2,7,1,8,9};
vector<int>
vec(a,a+5);
vector <int>
vect= twoSum(vec,15);
return 1;