首页 > 代码库 > LeetCode-Two Sum III - Data structure design
LeetCode-Two Sum III - Data structure design
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) -> truefind(7) -> false
Analysis:
Use O(1) add and O(n) find.
Solution:
public class TwoSum { HashMap<Integer,Integer> numCounts = new HashMap<Integer,Integer>(); List<Integer> nums = new ArrayList<Integer>(); // Add the number to an internal data structure. public void add(int number) { if (numCounts.containsKey(number)){ numCounts.put(number,numCounts.get(number)+1); } else { nums.add(number); numCounts.put(number,1); } } // Find if there exists any pair of numbers which sum is equal to the value. public boolean find(int value) { for (int num : nums){ int otherNum = value - num; boolean validPair = (otherNum==num) ? (numCounts.get(num)>=2) : numCounts.containsKey(otherNum); if (validPair){ return true; } } return false; }}// Your TwoSum object will be instantiated and called as such:// TwoSum twoSum = new TwoSum();// twoSum.add(number);// twoSum.find(value);
LeetCode-Two Sum III - Data structure design
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。