本博客主要基于LeetCode官方题解
Question
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].UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.
Brute Force Way
Result: Accepted Time: 668ms
This way is very simple，Loop through each element and find if there is another value that equals to .
Solution in CPP:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
const int len = nums.size();
for(int i = 0; i < len; i++)
for(int j = i + 1; j < len; j++)
if(nums[i] + nums[j] == target)
return vector<int>(i,j);
return vector<int>();
}
};
Complexity Analysis
- Time Complexity:
- Space Complexity:
Binary Search Way
Result: Accepted Time: 12ms
In this way, we use a struct to record the value and its index, and sort the vector. Then we loop through each value and use binary search to find if there is another value that equals to .
class Solution {
struct node{
int n,pos;
bool operator < (const node & rhs) const
{ return this->n < rhs.n;}
node(int v=0,int idx=0):n(v),pos(idx){}
};
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<node> tmp(nums.size());
for(int i=0;i<nums.size();i++)
tmp[i] = node(nums[i],i);
sort(tmp.begin(),tmp.end());
for(auto now = tmp.begin();now != tmp.end(); ++now)
{
auto it= lower_bound(tmp.begin(),tmp.end(),node(target - now->n));
if(now != it && it != tmp.end() && it->n == target - now->n)
return vector<int>{now->pos,it->pos};
}
return vector<int>();
}
};
Complexity Analysis
- Time Complexity:
- Space Complexity:
Two Pointers Way
Result: Accepted Time: 12ms
class Solution {
struct Node{
int n,pos;
Node(int v=0,int idx=0):n(v),pos(idx){}
bool operator < (const Node & rhs) const
{ return this->n < rhs.n;}
};
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<Node> tmp(nums.size());
for(int i=0;i<nums.size();i++)
tmp[i] = Node(nums[i],i);
sort(tmp.begin(),tmp.end());
int left = 0, right = nums.size() - 1;
while(left < right)
{
int sum = tmp[left].n + tmp[right].n;
if(sum > target)
right --;
else if(sum == target)
return vector<int>{tmp[left].pos,tmp[right].pos};
else left ++;
}
return vector<int>();
}
};
Complexity Analysis
- Time Complexity:
- Space Complexity:
Two-Pass Hash Table
Result: Accepted Time: 20ms
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> mp;
int index = 0;
for(const auto & x:nums)
mp[x] = index++;
index = 0;
for(const auto & x:nums)
if(++index && mp.count(target-x) && mp[target-x]!=index-1)
return vector<int>{index-1,mp[target-x]};
return vector<int>();
}
};
Complexity Analysis
- Time Complexity:
- Space Complexity:
One Pass Hash Table
Result: Accepted Time: 20ms
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> mp;
int index = 0;
for(const auto & x:nums){
if(mp.count(target-x))
return vector<int>{index,mp[target-x]};
mp[x] = index++;
}
return vector<int>();
}
};
Complexity Analysis
- Time Complexity:
- Space Complexity: