TwoSumIIIDataStructureDesign [source code]

public class TwoSumIIIDataStructureDesign {
static
/******************************************************************************/
public class TwoSum {
    List<Integer> ls = new LinkedList<>();
    Set<Integer> bag = new HashSet<>();

    /** Initialize your data structure here. */
    public TwoSum() {

    }

    /** Add the number to an internal data structure.. */
    public void add(int number) {
        ls.add(number);
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (int i : ls) {
            if (bag.contains(value - i)) return true;
            else bag.add(i);
        }
        return false;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        TwoSumIIIDataStructureDesign.TwoSum tester = new TwoSumIIIDataStructureDesign.TwoSum();
    }
}

首先这样一个设计题, 可以假定的一个条件是, add被call的次数应该是大量少于find的. 感觉题目的核心就是选择一个合适的数据结构让find的cost尽可能的低, 来支持大量的query;

那么相对的, add或许可以稍微大一点;

我这里的做法就是让add很昂贵(每次都是O(N)), 但是find很cheap. 但是OJ好像不认同这种理解, 最后超时了;
超时的这个case有大量的add, 完全就是故意的:

public class TwoSum {  
    List<Integer> ls = new LinkedList<>();  
    Set<Integer> bag = new HashSet<>();  

    public TwoSum() {  

    }  

    public void add(int number) {  
        for (int i : ls) {  
            bag.add(i + number);  
        }  
        ls.add(number);  
    }  

    public boolean find(int value) {  
        return bag.contains(value);  
    }  
}

最后只能用最土的方法做了一个, 不过速度很不好: 484ms (4%).
LinkedList换成ArrayList稍微快了一点, 不知道为什么;

discussion上面有人跟我提出了类似的观点, 一定要分清楚到底add和find哪个多:

The big data test only have the condition that lots of add and few find. 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.

但是下面有人提出这个观点:

Don't forget space trade-off.
Storing all possible sum may lead to O(n2) space.

这个倒是我没有想到的一个问题; 我现在谈到分析算法还是局限在time的范围内, 很多时候space的影响完全无法忽略;

这个人的算法在对于add expensive的情况下, 有一个小优化:

public void add(int number) {  
    if(num.contains(number)){  
        sum.add(number * 2);  
    }else{  
        Iterator<Integer> iter = num.iterator();  
        while(iter.hasNext()){  
            sum.add(iter.next() + number);  
        }  
        num.add(number);  
    }  
}

it is a clever optimization if you think of it. The problem is a 2-sum so the only possible new sum that could be added is number*2. You don't have to iterate again through the entire set and add all the sums.

这个是discussion里面大部分的解的样子:

public class TwoSum {  
    private HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();  

    public void add(int number) {  
        map.put(number, map.containsKey(number) ? map.get(number) + 1 : 1);  
    }  

    public boolean find(int value) {  
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {  
            int i = entry.getKey();  
            int j = value - i;  
            if ((i == j && entry.getValue() > 1) || (i != j && map.containsKey(j))) {  
                return true;  
            }  
        }  
        return false;  
    }  
}

也没什么特别创新的地方, 就是用map来保存counts, 然后后面处理的时候稍微区分一下, trivial的很;
不过话说回来, 真要是面试的时候, 面试官就是死磕问你就对着这个算法要你优化, 好像除了这些trivial的优化也没有什么好东西了;
感觉在学习算法的时候可以不管这些trivial的优化, 但是自己还是要适当总结一下, 然后每次面试之前稍微看一下这个checklist, 这样真的倒霉碰到这种trivial优化题, 知道有什么东西可以讲;

这里的这个trivial优化的内容, 跟上面那个set的方法的, 都是一个用count来代替 duplicate presence的概念的应用而已;

Problem Description

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
Difficulty:Easy
Total Accepted:27.3K
Total Submissions:112.8K
Contributor: LeetCode
Companies
linkedin
Related Topics
hash table design
Similar Questions
Two Sum Unique Word Abbreviation

/**

• Your TwoSum object will be instantiated and called as such:
• TwoSum obj = new TwoSum();
• obj.add(number);
• boolean param_2 = obj.find(value);
  */