Leetcode:No.170 Two Sum III - Data structure design

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.
Implement the TwoSum class:
TwoSum() Initializes the TwoSum object, with an empty array initially.
void add(int number) Adds number to the data structure.
boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.
Example 1:
Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]
Explanation
TwoSum twoSum = new TwoSum();
twoSum.add(1); // [] --> [1]
twoSum.add(3); // [1] --> [1,3]
twoSum.add(5); // [1,3] --> [1,3,5]
twoSum.find(4); // 1 + 3 = 4, return true
twoSum.find(7); // No two integers sum up to 7, return false
Constraints:
-10^5 <= number <= 10^5
-2^31 <= value <= 2^31 - 1
At most 5 * 10^4 calls will be made to add and find.

TwoSum数据结构版。初看起来还是很简单的，只要套上TwoSum的解法即可：

import java.util.*;

class TwoSum {

    // number - is duplicate map
    private final Map<Integer, Boolean> map;

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

    /**
     * Add the number to an internal data structure..
     */
    public void add(int number) {
        if (map.containsKey(number)) {
            map.put(number, true);
        } else {
            map.put(number, false);
        }
    }

    /**
     * Find if there exists any pair of numbers which sum is equal to the value.
     */
    public boolean find(int value) {
        for (int key : map.keySet()) {
            int t = value - key;
            // value = 2*key and we have duplicate
            if (t == key && map.get(t)) return true;
            if (t != key && map.containsKey(t)) return true;
        }
        return false;
    }
}

时间效率上，add是O（1），find是O（N），N是此时map中key的数量。
这种做法能AC，但是就最后的运行时间来看，属于相对后面的位置。

image.png

那么前面的都是怎么做的呢？
我参考了前面的做法，发现诀窍就是：充分利用题目给出的范围限制，然后用Array代替Map。
用Array代替Map，需要注意这些点：

Map的key可用Array的index来替代；
Map的value可用Array的value来替代；
Map的遍历是一个问题，因为假如直接遍历Array，效率会低很多。需要额外的数据结构来协助映射。

-10^5 <= number <= 10^5

这一个限制是很有利用价值的。因为Array的index不能为负数，我们需要给number加上10^5转化为自然数。也就是说，开一个[0, 200000]的Array，就可囊括所有number。
number已经加了10^5，它们的和自然就加了2倍这么多，也就是说和会在[0, 400000]这个区间了。不过我们可以不用在意这个，毕竟当初的map也没有牵涉到和。
此外，需要另外维持一个数据结构来直接放number，这样就可以不用遍历整个[0，200000]了。大小的话，根据题目限制，不会超过50000个add。如使用Array需要记录它的实际大小，不然可用List/Set代替。
最后就是一点额外优化：动态记录存放number的最大最小值，这样可以先进行一次界限判断，即value>2*max||value<2*min时，是肯定无法满足条件的。
注意我们选择int Array而不是Boolean，这是因为，在map当中key存不存在就是一个信息，也就是说有不存在，true和false3种，所以boolean就够了；而这里index已经存在了，所以boolean是不够承载3种信息的，要用int。

import java.util.*;

public class TwoSum {

    private final int[] arr;
    private final Set<Integer> nums;
    private int min = 100000;
    private int max = -100000;

    /**
     * Initialize your data structure here.
     */
    public TwoSum() {
        arr = new int[200001];
        nums = new HashSet<>();
    }

    /**
     * Add the number to an internal data structure..
     */
    public void add(int number) {
        if (arr[number + 100000] == 0) {
            nums.add(number);
            min = Math.min(min, number);
            max = Math.max(max, number);
        }
        arr[number + 100000]++;
    }

    /**
     * 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 n : nums) {
            int t = value - n;
            switch (arr[t + 100000]) {
                case 0:
                    break;
                case 1:
                    if (t != n) return true;
                    break;
                default:
                    return true;
            }
        }
        return false;
    }
}

现在运行时间就短多了：

image.png

更进一步，Set我也不要：

class TwoSum {

    private final int[] arr;
    private final int[] nums;
    int i = 0;
    private int min = 100000;
    private int max = -100000;

    /**
     * Initialize your data structure here.
     */
    public TwoSum() {
        arr = new int[200001];
        nums = new int[50000];
    }

    /**
     * Add the number to an internal data structure..
     */
    public void add(int number) {
        if (arr[number + 100000] == 0) {
            nums[i] = number;
            i++;
            min = Math.min(min, number);
            max = Math.max(max, number);
        }
        arr[number + 100000]++;
    }

    /**
     * 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 j = 0; j < i; j++) {
            int n = nums[j];
            int t = value - n;
            switch (arr[t + 100000]) {
                case 0:
                    break;
                case 1:
                    if (t != n) return true;
                    break;
                default:
                    return true;
            }
        }
        return false;
    }
}

还是有提升的：

image.png

总结：
这道题算法倒是其次，主要还是优化有点意思。虽然面试过程中不要求做出这些优化，但是提一提还是可以的。至于实际应用，则要考量是不是性能瓶颈，因为毕竟牺牲了可读性。总而言之，可以不用，但最好知道有这么回事。