170.Two Sum III - Data structure design
1.Description(M)
Design and implement a TwoSum class. It should support the following operations:add
andfind
.
add
- Add the number to an internal data structure.
find
- Find if there exists any pair of numbers which sum is equal to the value.
Example
add(1); add(3); add(5);
find(4) // return true
find(7) // return false
2.Code
我们把每个数字和其出现的次数建立映射,然后我们遍历哈希表,对于每个值,
我们先求出此值和目标值之间的差值t,然后我们需要分两种情况来看,
如果当前值不等于差值t,那么只要哈希表中有差值t就返回True,
或者是当差值t等于当前值时,如果此时哈希表的映射次数大于1,则表示哈希表中还有另一个和当前值相等的数字,二者相加就是目标值(就是target 等于两倍的当前元素)
public class Solution_607 {
HashMap<Integer,Integer> map=new HashMap<Integer,Integer>();
// Add the number to an internal data structure.
public void add(int number) {
if(!map.containsKey(number)){
map.put(number, 1);
}else{
map.put(number, map.get(number)+1);
}
}
// Find if there exists any pair of numbers which sum is equal to the value.
public boolean find(int value) {
for(Integer element:map.keySet()){
if(map.containsKey(value-element)){
//in case that value=element*2;
if(value-element!=element){
return true;
}else{
if(map.get(element)>1){
return true;
}
}
}
}
return false;
}
}
//Your TwoSum object will be instantiated and called as such:
//TwoSum twoSum = new TwoSum();
//twoSum.add(number);
//twoSum.find(value);
这里我们稍微修改一下上面的问题。我们设计一个类,拥有两个 API:
class TwoSum {
// 向数据结构中添加一个数 number
public void add(int number);
// 寻找当前数据结构中是否存在两个数的和为 value
public boolean find(int value);
}
如何实现这两个 API 呢,我们可以仿照上一道题目,使用一个哈希表辅助 find
方法:
class TwoSum {
Map<Integer, Integer> freq = new HashMap<>();
public void add(int number) {
// 记录 number 出现的次数
freq.put(number, freq.getOrDefault(number, 0) + 1);
}
public boolean find(int value) {
for (Integer key : freq.keySet()) {
int other = value - key;
// 情况一
if (other == key && freq.get(key) > 1)
return true;
// 情况二
if (other != key && freq.containsKey(other))
return true;
}
return false;
}
}
进行 find
的时候有两种情况,举个例子:
情况一:add
了 [3,3,2,5]
之后,执行 find(6)
,由于 3 出现了两次,3 + 3 = 6,所以返回 true。
情况二:add
了 [3,3,2,5]
之后,执行 find(7)
,那么 key
为 2,other
为 5 时算法可以返回 true。
除了上述两种情况外,find
只能返回 false 了。
对于这个解法的时间复杂度呢,add
方法是 O(1),find
方法是 O(N),空间复杂度为 O(N),和上一道题目比较类似。
但是对于 API 的设计,是需要考虑现实情况的。比如说,我们设计的这个类,使用 find
方法非常频繁,那么每次都要 O(N) 的时间,岂不是很浪费费时间吗?对于这种情况,我们是否可以做些优化呢?
是的,对于频繁使用 find
方法的场景,我们可以进行优化。我们可以参考上一道题目的暴力解法,借助哈希集合来针对性优化 find
方法:
class TwoSum {
Set<Integer> sum = new HashSet<>();
List<Integer> nums = new ArrayList<>();
public void add(int number) {
// 记录所有可能组成的和
for (int n : nums)
sum.add(n + number);
nums.add(number);
}
public boolean find(int value) {
return sum.contains(value);
}
}
这样 sum
中就储存了所有加入数字可能组成的和,每次 find
只要花费 O(1) 的时间在集合中判断一下是否存在就行了,显然非常适合频繁使用 find
的场景。
Last updated
Was this helpful?