【LeetCode 0170】【哈希】两数之和(3) 数据结构设计

https://leetcode.com/problems/two-sum-iii-data-structure-design/

描述

Design and implement a TwoSum class. It should support the following operations: add and find.
add(input) – Add the number input to an internal data structure.
find(value) – 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

题解

• 暴力法（哈希+数组）：计算每一对数字之和放入hashmap，O(n²)个存储空间，同时需要记住已经加入的N个数字，add时，需要与每个已加入的数字做加法存入hashmap，find时，只需要O(1)时间复杂度
• 二分插入+双指针：保持已经插入的数字有序，add时查找插入位置插入,find时使用双指针O(n)时间复杂度
• 高效哈希法，只需要存储所有插入的数字，为插入数据为key,次数为value(注意哈希中存在多个相同的数字)

function TwoSum(){this.hashmap = {};
}
TwoSum.prototype.add = function(e){if(null == this.hashmap[e]){this.hashmap[e] = 1;}else{this.hashmap[e] ++;}
}
TwoSum.prototype.find = function(sum){for(let current in this.hashmap){let antoher = sum-current ;if(antoher == current && this.hashmap[current] > 1){//存在 多个相同的valuesreturn true;}else if(null != this.hashmap[antoher]){// 存在不同的2个数字之和为sumreturn true}}return false
}