LeetCode 1. Two Sum
2024-08-31 18:30:20
Problem: 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].
该题最容易想到的暴力解法就是两层循环,逐对相加与target比较。其代价过大,代码为:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
unordered_map<int,int> hash;
for(int i = ; i < nums.size(); i++)
{
int num_to_find = target - nums[i];
if(hash.find(num_to_find) != hash.end())
{
result.push_back(hash[num_to_find]);
result.push_back(i);
return result;
}
else
{
hash[nums[i]] = i;
}
}
return result;
}
};
时间复杂度为O(n)的做法是只遍历一次vector,然后用hash表的find快速查找存储的数字。其代码如下:
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
unordered_map<int,int> hash;
for(int i = ; i < nums.size(); i++)
{
int num_to_find = target - nums[i];
if(hash.find(num_to_find) != hash.end())
{
result.push_back(hash[num_to_find]);
result.push_back(i);
return result;
}
else
{
hash[nums[i]] = i;
}
}
return result;
}
};
已遇到多题巧用hash table(unordered_map)简化算法的方法,注意hash table的使用!
最新文章
- 小菜学习Winform(一)贪吃蛇2
- org.springframework.web.servlet.DispatcherServlet noHandlerFound
- CSS3选择器的研究,案例
- cocos2dx 锁定30帧设置
- 机器学习(Machine Learning)&;深度学习(Deep Learning)资料【转】
- VC 为静态控件添加事件(修改ID号以后添加事件)
- 学习NodeJS第一天:node.js引言
- 蜗牛爱课- CGAffineTransformMakeRotation 实现一张图片的自动旋转
- JQuery - 根据节点获取对应的id,可用于留言板
- 自定义UICollectionViewLayout 布局实现瀑布流
- sudo su 和 sudo -s【转】
- python numpy中数组.min()
- time&;datetime模块详解
- 在quartz的Job中获得Spring的WebApplicationContext或ServletContext
- 保证java的jar包在后台运行
- Javascript中Closure及其相关概念
- 【转】decorView和window之间的层级及关系
- 【bzoj3573】 Hnoi2014—米特运输
- PHP各种经典算法
- c++之旅:函数模板