unreasonably effective

you can be sloppy, as long as you are rigorous

LeetCode 170: Two Sum III – Data structure design

link

We can keep a map: {number -> count}. To find two numbers that sum up to value, we can iterate through the map. For x, (value – x) must be in the map. If x and (value – x) are equal, then the count of x must be at least 2.

Say, there are n distinct numbers.

OperationTimeSpace
__init__\mathcal{O}(1)\mathcal{O}(1)
add\mathcal{O}(1)\mathcal{O}(1)
find\mathcal{O}(n)\mathcal{O}(1)
class TwoSum:

    def __init__(self):
        self.num_map = {}

    def add(self, number: int) -> None:
        if number not in self.num_map:
            self.num_map[number] = 1
        else:
            self.num_map[number] += 1

    def find(self, value: int) -> bool:
        for x, count in self.num_map.items():
            y = value - x
            if x == y:
                if count > 1:
                    return True
                continue
                
            if y in self.num_map:
                return True
        
        return False


# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)

tanvirdotzaman

,

Leave a comment