leetcode第一题
two sum C版本
- 暴力搜索法
int* twoSum(int* nums, int numsSize, int target) {
int i,j;
//int result[2];
int * result = (int *)malloc(sizeof(int) * 2);
for(i=0;i<numsSize;i++)
{
for(j=i+1;j<numsSize;j++)
{
if(nums[i]+nums[j]==target)
{
result[0]=i;
result[1]=j;
break;
}
}
}
return result;
}
时间复杂度O(n2) 看结果可以用hash表搜索减少时间。以后可以进一步优化。
今天学习一下Hash的原理，学习c++版本的解法
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> mapping;
vector<int> result;
for (int i = 0; i < nums.size(); i++)
{
mapping[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i++)
{
const int gap = target - nums[i];
if (mapping.find(gap) != mapping.end() && mapping[gap] > i)
{
result.push_back(i);
result.push_back(mapping[gap] );
break;
}
}
return result;
}
};
由于hash map中包含的元素很少，可认为是直接寻址，单一查找一个元素的时间复杂度为O(1)。经过外层n个数的循环，整体时间复杂度为O(n)。
