博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
170. Two Sum III - Data structure design - Easy
阅读量:5881 次
发布时间:2019-06-19

本文共 1397 字,大约阅读时间需要 4 分钟。

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.

Example 1:

add(1); add(3); add(5);find(4) -> truefind(7) -> false

Example 2:

add(3); add(1); add(2);find(3) -> truefind(6) -> false

 

用hashmap存新加入的元素和频率

add直接把元素加进hashmap。find遍历整个map,分两种情况,如果k和v相同,对应频率要大于1;如果不同,只要map中存在key=v即可。

时间:add - O(1), find - O(N),空间:O(N)

class TwoSum {    HashMap
map; /** Initialize your data structure here. */ public TwoSum() { map = new HashMap<>(); } /** Add the number to an internal data structure.. */ public void add(int number) { map.put(number, map.getOrDefault(number, 0) + 1); } /** Find if there exists any pair of numbers which sum is equal to the value. */ public boolean find(int value) { for(Map.Entry
entry : map.entrySet()) { int k = entry.getKey(); int v = value - k; if((k != v && map.containsKey(v)) || (k == v && map.get(v) > 1)) return true; } return false; }}/** * Your TwoSum object will be instantiated and called as such: * TwoSum obj = new TwoSum(); * obj.add(number); * boolean param_2 = obj.find(value); */

 

转载于:https://www.cnblogs.com/fatttcat/p/10050186.html

你可能感兴趣的文章
python
查看>>
SIEM在PCI DSS和安全等级保护合规性中的作用
查看>>
奥马冰箱:用设计创新突破行业“天花板”
查看>>
Oracle Database 11g SQL开发指南
查看>>
ACM一些小的注意事项 持续更新ing
查看>>
Go语言之单元测试
查看>>
查找字符串里出现次数最多的字符。(map的遍历方法)
查看>>
python对象和类
查看>>
Linux Virtualiztion—概述
查看>>
ssh 免密码登录
查看>>
教学笔记-方法的重载与重写
查看>>
Target runtime Apache Tomcat 6.0 is not defined 解决方法
查看>>
【浙大网新图灵通讯】无废话简单高效C#编码规范20100612
查看>>
实现基于组织机构的数据集权限系统的设计思路讲解【提供完整数据库设计下载】...
查看>>
docker-py execute echo无效
查看>>
Spring Boot Redis Cache应用
查看>>
SQL Server 监视(Monitoring)体系架构
查看>>
SQLSERVER群集故障转移笔记
查看>>
我的友情链接
查看>>
业务相关同步机制
查看>>