美文网首页Leetcode每日两题程序员
Leetcode 170. Two Sum III - Data

Leetcode 170. Two Sum III - Data

作者: ShutLove | 来源:发表于2017-11-10 17:56 被阅读6次

    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

    思路:自己是用了一个map和一个set,add的时候效率较低,get的时候效率高,提交后是tle。因为case中add操作多,get操作少,如果get中进行遍历的话是可以通过的。

    HashMap<Integer, Integer> map = new HashMap<>();
    HashSet<Integer> set = new HashSet<>();
    
    public FN_TwoSumIII() {
    
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (map.containsKey(number)) {
            if (map.get(number) > 1) {
                return;
            } else {
                map.put(number, 2);
                set.add(number*2);
            }
        } else {
            for (Integer num : map.keySet()) {
                set.add(num + number);
            }
            map.put(number, 1);
        }
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        return set.contains(value);
    }
    

    答案中还有一个方法很巧妙,每次get的时候判断判断target和当前遍历值的差值是否存在于map中。

    private List<Integer> list = new ArrayList<Integer>();
    private Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
    // Add the number to an internal data structure.
    public void add(int number) {
        if (map.containsKey(number)) map.put(number, map.get(number) + 1);
        else {
            map.put(number, 1);
            list.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 = 0; i < list.size(); i++){
            int num1 = list.get(i), num2 = value - num1;
            if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) return true;
        }
        return false;
    }

    相关文章

      网友评论

        本文标题:Leetcode 170. Two Sum III - Data

        本文链接:https://www.haomeiwen.com/subject/fyfimxtx.html