TwoSumIIIDataStructureDesignOPT [source code]

public class TwoSumIIIDataStructureDesignOPT {
static
/******************************************************************************/
public class TwoSum {
    private Set<Integer> closeSet;
    private List<Integer> list;
    private Map<Integer, Integer> map;
    private int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;

    /** Initialize your data structure here. */
    public TwoSum() {
        closeSet = new HashSet<>();
        list = new ArrayList<>();
        map = new HashMap<>();
    }

    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (!closeSet.contains(number)) {
            min = Math.min(min, number);
            max = Math.max(max, number);
            if (map.containsKey(number)) closeSet.add(number);
            map.put(number, list.size());
            list.add(number);
        }
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        if (value / 2 > max || value / 2 < min) return false;

        for (int i = 0; i < list.size(); i++) {
            int target = value - list.get(i);
            if (map.containsKey(target) && map.get(target) > i)
                return true;
        }
        return false;
    }
}
/******************************************************************************/

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

submission最优解, 意外的121(99.87), 这个就很厉害了;

仔细看了一下, 这个算法好像其实也没有多少优化, 无非就是首先加了一个max和min的判断, 这个我看了一下其他几个版本的submission最优解好像也都加了;

其次就是这里这个closeSet的作用.
这个东西的作用其实好像就是假如一个数字被add超过三次, 那么从第三次开始的所有的add都无视. 这个也就是一个优化; 因为从2sum的角度上来说, 第三次及以后的出现确实就已经没有什么作用了;

刚开始拿到这个代码的时候看不懂各个变量到底是什么意思, 毕竟是submission上面直接抓下来的代码, 没有任何的解释, 但是我们之前也碰到过这样的情况, 当你不知道一个变量代表的到底是什么意思的时候, 直接寻找这个变量被更新和被access的地方, 尤其是被更新的地方;

这里的几个变量被更新的地方都是在add里面, 所以直接盯着add的代码看就行了;
如果还是感觉看不懂, 那就跑几个例子, 我跑的例子是1,2,3,3,3,4, 也不算复杂的一个例子, 跑一下大概就知道代码是什么意思了;
举例子的时候不要担心自己的例子不够representative, 无法提现这个代码逻辑的subtlety, 只要你肯去跑这个例子, 总归是比你不跑要好的, 就算你现在这个例子不能彻底体现这个代码的逻辑, 在跑的过程中你大概就会发现代码逻辑的细节, 并且想到如何修改当前的例子来诱导代码的subtlety;

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);
  */