Leetcode: Two Sum III - Data structure design
LeetCode Data sum Design two III Structure
2023-09-11 14:14:08 时间
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
The trade off should be considered: In fact, there has to be one operation's time complexity is O(n) and the other is O(1), no matter add or find. So clearly there's trade off when solve this problem, prefer quick find or quick add.
if there are more find, add can be pre-done
1 public class TwoSum { 2 Set<Integer> sum; 3 Set<Integer> num; 4 5 TwoSum(){ 6 sum = new HashSet<Integer>(); 7 num = new HashSet<Integer>(); 8 } 9 // Add the number to an internal data structure. 10 public void add(int number) { 11 if(num.contains(number)){ 12 sum.add(number * 2); 13 }else{ 14 Iterator<Integer> iter = num.iterator(); 15 while(iter.hasNext()){ 16 sum.add(iter.next() + number); 17 } 18 num.add(number); 19 } 20 } 21 22 // Find if there exists any pair of numbers which sum is equal to the value. 23 public boolean find(int value) { 24 return sum.contains(value); 25 } 26 }
more add:
1 public class TwoSum { 2 HashMap<Integer, Integer> map; 3 public TwoSum() { 4 map = new HashMap<Integer, Integer>(); 5 } 6 7 public void add(int x) { 8 if (map.containsKey(x)) { 9 map.put(x, map.get(x)+1); 10 } 11 else { 12 map.put(x, 1); 13 } 14 } 15 16 public boolean find(int target) { 17 for (int i : map.keySet()) { 18 if (map.containsKey(target-i)) { 19 if (target - i != i) return true; 20 else if (map.get(i) >= 2) return true; 21 } 22 } 23 return false; 24 } 25 }
注意17行的map.KeySet() return是一个Set形式的key的集合,Set是Collection的Subinterface, 所以这种for循环方法对Set也适用。而且即使key理论上是Integer, for循环前面的元素还是可以写成int:for(int i : map.keySet())
相关文章
- Java实现 LeetCode 633 平方数之和(暴力大法)
- Java实现 LeetCode 623 在二叉树中增加一行(遍历树)
- Java实现 LeetCode 448 找到所有数组中消失的数字
- Java实现 LeetCode 400 第N个数字
- Java实现 LeetCode 201 数字范围按位与
- Java实现 LeetCode 141 环形链表
- LeetCode:110_Balanced Binary Tree | 平衡二叉树 | Easy
- [React Testing] Use Generated Data in Tests with tests-data-bot to Improve Test Maintainability
- LeetCode-1694. 重新格式化电话号码【字符串,分块】
- Python 刷Leetcode题库,顺带学英语单词(18)
- 【LeetCode 23】合并K个排序链表
- LeetCode:Remove Duplicates from Sorted Array
- [Leetcode]-Min Stack
- leetcode - Reverse Linked List II
- leetcode 108. Convert Sorted Array to Binary Search Tree
- 【Mac系统】Vscode使用LeetCode插件报错‘leetcode.toggleLeetCodeCn‘ not found
- 【LeetCode】50. Pow(x,n)
- 【LeetCode】剑指 Offer II 109. 开密码锁