✡ leetcode 170. Two Sum III - Data structure design 设计two sum模式 --------- java

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

设计一个two sum 的类。包含add和find两种操作方式。

1、使用HashMap和HashSet实现。

public class TwoSum {

    Map<Integer,Integer> map = new HashMap<Integer,Integer>();

    Set<Integer> set = new HashSet<Integer>();

    // Add the number to an internal data structure.

    public void add(int number) {

        if (set.contains(number)){

            map.put(number, 2);

        }else {

            set.add(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) {

        for (int num : set){

            if (num == value - num){

                if (map.get(num) == 2){

                    return true;

                }

            } else if (set.contains(value - num)){

                return true;

            }

        }

        return false;

    }

}

// Your TwoSum object will be instantiated and called as such:

// TwoSum twoSum = new TwoSum();

// twoSum.add(number);

// twoSum.find(value);

2、使用HashMap 和 List（也可以只使用一个HashMap，记录一或者2即可。）

public class TwoSum {

    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;

    }

}

// Your TwoSum object will be instantiated and called as such:

// TwoSum twoSum = new TwoSum();

// twoSum.add(number);

// twoSum.find(value);

3、为什么要使用一个List，因为在遍历操作的时候，List要比Map或者Set快得多，使用一个List可以用空间换取时间。

巴特西

✡ leetcode 170. Two Sum III - Data structure design 设计two sum模式 --------- java

最新文章

热门文章