Two Sum III

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

A simpler approach is to store each input into a hash table with the input as key and its count as value. To find if a pair sum exists, just iterate through the hash table in O(n) runtime. Make sure you are able to handle duplicates correctly. 

 

 1 public class TwoSum{
 2     //Firstly, we create a hashmap
 3     Map<Integer, Integer> hm = new HashMap<>();
 4 
 5     public void add(int number){
 6         int count = hm.containsKey(number) ? hm.get(number): 0;
 7         hm.put(number, count +1);
 8    }
 9 
10    public boolean find(int value){
11         //The Map.Entry interface enables you to work with a map entry
12         for(Map.Entry<Integer, Integer> entry: hm.entrySet()){
13             int num = entry.getKey();
14             int r = value - num;
15             if(r == num){
16                 // For duplicates, ensure there are at least two individual numbers
17                 if(entry.getValue() >= 2) return true;
18              }else if(hm.containsKey(r)){
19                 return true;
20             }
21         }
22         return false;
23   }
24 }                    

 

更多相关文章
  • Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only n
  • LeetCode216. Combination Sum III
    Combination Sum III Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each co
  • 原题链接在这里:https://leetcode.com/problems/combination-sum-iii/ 与Combination Sum II相似,不同的是中不是所有元素相加,只是k个元素相加. 所以在把item的copy 加到res前需要同时满足item.size() == k 和
  • Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the
  • LeetCode 筆記27 Two Sum III
    Design and implement a TwoSum class. It shoul
  • Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be
  •   Path Sum I  刚开始想用回溯算法,但是后来发现有负数的情况下这种方法不行,所以就不能用回溯算法了,直接用简单粗暴的递归算法. /** * Definition for binary tree * struct TreeNode { * int val; * TreeNode *left
  • Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be
一周排行
  • 1.修改sshd服务器的配置文件/etc/ssh/sshd_config,将部分参数参照如下修改,增强安全性. Port 6688 系统缺省使用22号端口,将监听端口更改为其他数值(最好是1024以上的高端口,以免和 ...
  • 问题:当打开word时,提示让"安全模式"才能启动或者提示"Microsoft Office Word遇到问题需要关闭". 解决:我们不需要通过安全模式启动,原因是Normal ...
  • MFC 高仿Flappy bird 桌面版
        这是今年年初做的东西,一直没有时间整理,现在拿出来分享下~   目录 开发背景 开 ...
  • 


    		    ESXI更改QLogic光纖HBA卡隊列深度
    有时候我们要更改HBA卡的队列深度,以满足性能调试处理,在这里我会告诉你如何将深度队列从3
  • easyui-menu里的菜单项是从后端获取的,而这个组件提供的API配置只能设置一个固定宽度,当获取的菜单项字数较多时有可能显示不全.解决方法如下: <style> .myClass{font-size ...
  • 题目链接: 戳我 题目大意: 给一些人,包括姓名(保证唯一,只有小写)和 杀人数,当杀人数相同时,按照姓名的字典序小的在前.要求先输出每个人的排序后的名字和次序. M询问,每次询问一个人名,输出这个人的 主次序(比他
  • sharepoint2010配置個人網站的offical方法  來自Jetluning的專欄
    Configuring My Site in SharePoint 201   Share
  • ASP.NET MVC  CheckBoxFor的int  to bool
    当我们使用CheckBoxFor类型需要使用bool ,可以将 int转换成bool &l ...
  • 概要:有一树形结构的网络,要在一些结点安装服务器使得不是服务器的结点周围恰好有一个服务器,问服务器最小数量. 先转成有根树(枚举子节点的时候忽略其父亲),然后dp[u][s]表示u的子树安装服务器的最小数量,影响决策
  • 第一部分:TSql Output 关键字有两种应用场景 1,作为存储过程的参数类型,从存储过程中返回数据 2,返回受 INSERT.UPDATE.DELETE 或 MERGE 语句影响的各行中的信息,可以捕获嵌入到