当前位置：首页 > article >正文

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

article 2024/9/23 18:29:49

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){
	   		//存在 多个相同的values
            return true;
	   }else if(null != this.hashmap[antoher]){
	   	   // 存在不同的2个数字之和为sum
	   	   return true
	   }
    }
    return false
}