1. Two Sum
题目
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].
解析
class Solution_1 {
public:
// O(n^2)
vector<int> twoSum(vector<int> &numbers, int target) {
vector<int> vec;
if (numbers.size()==0)
{
return vec;
}
for (int i = 0; i < numbers.size()-1;i++)
{
for (int j = i + 1; j < numbers.size();j++)
{
if (numbers[i]+numbers[j]==target)
{
vec.push_back(i);
vec.push_back(j);
break;
}
}
}
return vec;
}
// 使用一个哈希表(unorder_map)来解，第一遍扫描，保存到哈希表中，第二遍扫，看target-n在不在哈希表中，时间复杂度为O(n)。
// 元素有重复的时候multi??
vector<int> twoSum(vector<int> a, int target) {
int i, j, k, l, m, n;
map<int, int>mymap;
map<int, int>::iterator it;
vector<int>ans;
for (i = 0; i < a.size(); i++){
it = mymap.find(target - a[i]);
if (it != mymap.end()){
ans.push_back(it->second);
ans.push_back(i);
return ans;
}
else{
mymap.insert(make_pair(a[i], i));
}
}
}
vector<int> twoSum1(vector<int>& nums, int target) {
vector<int> vec;
if (nums.size()==0)
{
return vec;
}
sort(nums.begin(), nums.end());
int start = 0, end = nums.size()-1;
while (start<end)
{
if (nums[start]+nums[end]==target)
{
vec.push_back(start);
vec.push_back(end);
break;
}
else if (nums[start] + nums[end] < target)
{
start++;
}
else
{
end--;
}
}
return vec; //返回值的排序后的index,不符合题意
}
};
题目来源