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

那么前面的都是怎么做的呢？
我參考了前面的做法鸿市，發(fā)現(xiàn)訣竅就是：充分利用題目給出的范圍限制锯梁，然后用Array代替Map即碗。
用Array代替Map，需要注意這些點：

Map的key可用Array的index來替代涝桅；
Map的value可用Array的value來替代拜姿；
Map的遍歷是一個問題，因為假如直接遍歷Array冯遂，效率會低很多蕊肥。需要額外的數據結構來協(xié)助映射。

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

這一個限制是很有利用價值的蛤肌。因為Array的index不能為負數壁却，我們需要給number加上10^5轉化為自然數。也就是說裸准，開一個[0, 200000]的Array展东，就可囊括所有number。
number已經加了10^5炒俱，它們的和自然就加了2倍這么多盐肃，也就是說和會在[0, 400000]這個區(qū)間了。不過我們可以不用在意這個权悟，畢竟當初的map也沒有牽涉到和砸王。
此外，需要另外維持一個數據結構來直接放number峦阁，這樣就可以不用遍歷整個[0谦铃，200000]了。大小的話榔昔，根據題目限制驹闰，不會超過50000個add。如使用Array需要記錄它的實際大小撒会，不然可用List/Set代替嘹朗。
最后就是一點額外優(yōu)化：動態(tài)記錄存放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;
    }
}

現(xiàn)在運行時間就短多了：

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

總結：
這道題算法倒是其次自阱，主要還是優(yōu)化有點意思。雖然面試過程中不要求做出這些優(yōu)化米酬，但是提一提還是可以的沛豌。至于實際應用，則要考量是不是性能瓶頸赃额，因為畢竟犧牲了可讀性加派。總而言之跳芳，可以不用芍锦，但最好知道有這么回事。