Two Sum I/II/III
要点:都是简单题,III就要注意如果value-num==num的情况,所以要count,并且count>1
https://repl.it/CrZG
错误点:
- TLE:defaultdict is slower than normal dict
- TLE:.keys() copies keys, it’s way slower
# Design and implement a TwoSum class. It should support the following operations: add and find.
# 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.
# For example,
# add(1); add(3); add(5);
# find(4) -> true
# find(7) -> false
# Hide Company Tags LinkedIn
# Hide Tags Hash Table Design
# Hide Similar Problems (E) Two Sum (E) Unique Word Abbreviation
from collections import defaultdict
class TwoSum(object):
def __init__(self):
"""
initialize your data structure here
"""
self.counts = defaultdict(int)
def add(self, number):
"""
Add the number to an internal data structure.
:rtype: nothing
"""
self.counts[number]+=1
def find(self, value):
"""
Find if there exists any pair of numbers which sum is equal to the value.
:type value: int
:rtype: bool
"""
for k in self.counts.keys():
if value-k not in self.counts or (k==value-k and self.counts[k]==1):
continue
return True
return False
# Your TwoSum object will be instantiated and called as such:
# twoSum = TwoSum()
# twoSum.add(number)
# twoSum.find(value)