LintCode 題解丨面試真題：兩數之和 III-資料結構設計

設計并實作一個 TwoSum 類。他需要支援以下操作:​add​ 和 ​find​。

​add​ -把這個數添加到内部的資料結構。

​find​ -是否存在任意一對數字之和等于這個值

線上評測位址：

LintCode 領扣

​

樣例 1:

add(1);add(3);add(5);

find(4)//傳回true

find(7)//傳回false

【題解】

使用哈希表的方法是最快的。

add 可以做到 O(1)

find 可以做到 O(n)

public class TwoSum {

private Map<Integer, Integer> counter;

public TwoSum() {
    counter = new HashMap<Integer, Integer>();
}

// Add the number to an internal data structure.
public void add(int number) {
    counter.put(number, counter.getOrDefault(number, 0) + 1);
}

// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
    for (Integer num1 : counter.keySet()) {
        int num2 = value - num1;
        int desiredCount = num1 == num2 ? 2 : 1;
        if (counter.getOrDefault(num2, 0) >= desiredCount) {
            return true;
        }
    }
    return false;
}           

}

// Your TwoSum object will be instantiated and called as such:// TwoSum twoSum = new TwoSum();// twoSum.add(number);// twoSum.find(value);

排序數組+雙指針的算法會逾時，但是大家可以看看是怎麼寫的，時間複雜度：

add O(n)

find O(n)

public List<Integer> nums;
public TwoSum() {
    nums = new ArrayList<Integer>();
}

public void add(int number) {
    nums.add(number);
    int index = nums.size() - 1;
    while (index > 0 && nums.get(index - 1) > nums.get(index)) {
        int temp = nums.get(index);
        nums.set(index, nums.get(index - 1));
        nums.set(index - 1, temp);
        index--;
    }
}

public boolean find(int value) {
    int left = 0, right = nums.size() - 1;
    while (left < right) {
        int twoSum = nums.get(left) + nums.get(right);
        if (twoSum < value) {
            left++;
        } else if (twoSum > value) {
            right--;
        } else {
            return true;
        }
    }
    return false;
}           

更多題解參考：

九章算法 - 幫助更多中國人找到好工作，矽谷頂尖IT企業工程師實時線上授課為你傳授面試技巧