设计并实现一个 TwoSum 的类,使该类需要支持 add 和 find 的操作。

    add 操作 - 对内部数据结构增加一个数。
    find 操作 - 寻找内部数据结构中是否存在一对整数,使得两数之和与给定的数相等。

    示例 1:

    add(1); add(3); add(5);
    find(4) -> true
    find(7) -> false
    示例 2:

    add(3); add(1); add(2);
    find(3) -> true
    find(6) -> false

    来源:力扣(LeetCode)
    链接:https://leetcode-cn.com/problems/two-sum-iii-data-structure-design

    思路:
    与两数之和思路类似,使用map保存每个数字出现的次数
    复杂度分析:
    时间复杂度:

    • add函数O(1)
    • find函数O(n)

    空间复杂度O(n)

    1. /**
    2. * Initialize your data structure here.
    3. */
    4. var TwoSum = function() {
    5. this.map = new Map();
    6. };
    7. /**
    8. * Add the number to an internal data structure..
    9. * @param {number} number
    10. * @return {void}
    11. */
    12. TwoSum.prototype.add = function(number) {
    13. if(this.map.has(number)){
    14. this.map.set(number,this.map.get(number)+1);
    15. }else{
    16. this.map.set(number,1);
    17. }
    18. };
    19. /**
    20. * Find if there exists any pair of numbers which sum is equal to the value.
    21. * @param {number} value
    22. * @return {boolean}
    23. */
    24. TwoSum.prototype.find = function(value) {
    25. for(let v of this.map.keys()){
    26. let other = value - v;
    27. if(other === v){
    28. if(this.map.get(other)>=2){
    29. return true;
    30. }
    31. }else {
    32. if(this.map.has(other)){
    33. return true;
    34. }
    35. }
    36. }
    37. return false;
    38. };
    39. /**
    40. * Your TwoSum object will be instantiated and called as such:
    41. * var obj = new TwoSum()
    42. * obj.add(number)
    43. * var param_2 = obj.find(value)
    44. */