首页 > 代码库 > 170. Two Sum III - Data structure design
170. Two Sum III - Data structure design
我自己的想法
1. 建一个list。
1）每次add就用Binary search找到插入的位置，插入O(logn)
2) 每次find就two pointer。O(n)
2. 一个arr
1）每次add直接加 O(1)
2）find就先sort，再two pointer. O(nlogn)
3. 建一个map，存每个数出现的次数.如果add常发生但是find不常发生
1）add就直接加o(1)
2) find就遍历map，找有没有target-cur的值。O(n)
4. 建两个set。一个存有的数，一个存有的可能的sum。适用于find常发生，而add不常发生的情况
1）add的时候把遍历set把所有可能的sum加入。O(n)
注意的是，如果该数已经在set里面了，那么只需要在sum set里加入这个数本身*2，不需要再遍历num set，因为加入第一个相同的数的时候已经算过一遍了
2) find的时候直接从sum set里面拿。O(1)
方法三代码：
1 import java.util.Map.Entry; 2 3 public class TwoSum { 4 Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 5 6 // Add the number to an internal data structure. 7 public void add(int number) { 8 map.put(number, map.containsKey(number)? map.get(number) + 1: 1); 9 }10 11 // Find if there exists any pair of numbers which sum is equal to the value.12 public boolean find(int value) {13 for(Map.Entry<Integer, Integer> entry: map.entrySet()) {14 int cur = entry.getKey();15 int target = value - cur;16 if((cur == target && entry.getValue() > 1) || (cur != target && map.containsKey(target))) {17 return true;18 }19 }20 return false;21 }22 }
方法四代码：
1 public class TwoSum { 2 Set<Integer> num = new HashSet<Integer>(); 3 Set<Integer> sum = new HashSet<Integer>(); 4 5 // Add the number to an internal data structure. 6 public void add(int number) { 7 if(num.contains(number)) { 8 sum.add(number + number); 9 } else {10 for(int each: num) {11 sum.add(each + number);12 }13 num.add(number);14 }15 }16 17 // Find if there exists any pair of numbers which sum is equal to the value.18 public boolean find(int value) {19 return sum.contains(value);20 }21 }
但是提交的时候LTE了，可能因为给的例子里面add太多了吧
170. Two Sum III - Data structure design
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。