170. Two Sum III - Data structure design【easy】
2024-08-29 08:28:27
170. Two Sum III - Data structure design【easy】
Design and implement a TwoSum class. It should support the following operations:add and find.
add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5);
find(4) -> true
find(7) -> false
这是一道收费题目,参考了grandyang的博客,感谢他!
解法一:
class TwoSum {
public:
void add(int number) {
++m[number];
}
bool find(int value) {
for (auto a : m) {
int t = value - a.first;
if ((t != a.first && m.count(t)) || (t == a.first && a.second > )) {
return true;
}
}
return false;
}
private:
unordered_map<int, int> m;
};
哈希表的解法,我们把每个数字和其出现的次数建立映射,然后我们遍历哈希表,对于每个值,我们先求出此值和目标值之间的差值t,然后我们需要分两种情况来看,如果当前值不等于差值t,那么只要哈希表中有差值t就返回True,或者是当差值t等于当前值时,如果此时哈希表的映射次数大于1,则表示哈希表中还有另一个和当前值相等的数字,二者相加就是目标值
解法二:
class TwoSum {
public:
void add(int number) {
s.insert(number);
}
bool find(int value) {
for (auto a : s) {
int cnt = a == value - a ? : ;
if (s.count(value - a) > cnt) {
return true;
}
}
return false;
}
private:
unordered_multiset<int> s;
};
另一种解法不用哈希表,而是unordered_multiset来做,但是原理和上面一样
参考自:http://www.cnblogs.com/grandyang/p/5184143.html
最新文章
- XCod5 SVN
- Atitit.加密算法ati Aes的框架设计
- jquery-validation-1.13.1 自定义验证正则
- Python自动化 【第十篇】:Python进阶-多进程/协程/事件驱动与Select\Poll\Epoll异步IO
- 【Javascript Demo】JS获取当前对象大小以及屏幕分辨率等
- BZOJ 3997 组合数学
- 28335 AD 转换
- jquery响应回车事件
- C语言复习笔记-17种小算法-解决实际问题
- 解析XML最快速的方式
- hdu1003 Max Sum(经典dp )
- HashTable与HashMap使用总结
- 一键安装LAMP
- 关于noip2017的感想
- 16.python-I/O模型
- XAML绑定到资源文件字符串时失败
- day23 模块引入的一些说明
- 实现textview竖排文字效果
- js 简单算法
- python中的对象(三)
热门文章
- [Contest20180313]灵大会议
- 【单调队列优化DP】BZOJ1855-[Scoi2010]股票交易
- 实用类String.length应用-用户名密码长度
- 【R笔记】R语言中的字符串处理函数
- linux下安装python2.7.5和MYSQLdb
- eth0: ERROR while getting interface flags: No such device
- JSON.parse(str),JSON.stringify(a)
- [Git] Git把Tag推送到远程仓库
- 【Hadoop】HDFS原理、元数据管理
- jQuery:多个AJAX/JSON请求相应单个回调