【LeetCode 1_数组_哈希表】Two Sum

【LeetCode 1_数组_哈希表】Two Sum

解法一:O(N)

 vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> numsHash;
vector<int> res; for (int i = ; i < nums.size(); ++i) {
int num_last = target - nums[i];
if (numsHash.find(num_last) != numsHash.end()) {
res.push_back(numsHash[num_last] + );
res.push_back(i + );
break;
} else {
numsHash[nums[i]] = i;
}
}
return res;
}

解法二:O(NlogN)

 vector<int> twoSum(vector<int>& nums, int target)
{
vector<int> res;
int lpos = , rpos = nums.size() - ;
sort(nums.begin(), nums.end());
while (lpos < rpos) {
int num = nums[lpos] + nums[rpos];
if (num == target) {
res.push_back(lpos + );
res.push_back(rpos + );
} else if (num > target) {
rpos--;
} else {
lpos++;
}
}
return res;
}

解法二也是不错的思路,空间复杂度O(1),但这个解法会超时。

上一篇:java面试题之HashMap和HashTable底层实现的区别


下一篇:linux 安装 Headless Chrome