leetcode_001 two sum

题意分析：从数组中找出和为target的索引

解题思路：1）双重循环，时间复杂度为O(n*n）； 2）用hash表实现，时间复杂度为O(n)

第一种方法实现双重循环求解

vector<int> twoSum1(vector<int> &nums, int target)
{
vector<int> result;
int len = nums.size();
if (len < 2)
return result;
for (int i = 0; i < len; i++)
{
for (int j = i + 1; j < len; j++)
{
if (nums[i] + nums[j] == target)
{
result.push_back(i);
result.push_back(j);
return result;
}
}
}
return result;
}

第二种方法实现hash表求解

vector<int> twoSum(vector<int> &nums, int target)
{
// 利用hash函数实现
vector<int> result;
map<int, int> mp;
for (int i = 0; i < nums.size(); i++)
{
if (!mp.count(nums[i]))
{
mp.insert(pair<int, int>(nums[i], i));
}
if (mp.count(target - nums[i]))
{
int n = mp[target - nums[i]];
if (n < i)
{
result.push_back(n);
result.push_back(i);
return result;
}
}
}
return result;
}

最后

以上就是开放彩虹为你收集整理的leetcode_001 two sum的全部内容，希望文章能够帮你解决leetcode_001 two sum所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。