Python Solution O(1) ADD and O(N) find


  • 0
    U
    class TwoSum(object):
    
        def __init__(self):
            """
            initialize your data structure here
            """
            self.numbers = []
            self.hash = {}
    
        def add(self, number):
            """
            Add the number to an internal data structure.
            :rtype: nothing
            """
            if number not in self.hash:
                self.hash[number] = 1
                self.numbers.append(number)
            else:
                self.hash[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 num in self.numbers:
                if value - num in self.hash:
                    if value - num == num and self.hash[num] == 1:
                        continue
                    return True
            
            return False
    
    # Your TwoSum object will be instantiated and called as such:
    # twoSum = TwoSum()
    # twoSum.add(number)
    # twoSum.find(value)
    

  • 0
    X
    This post is deleted!

  • 1
    U

    In add method we are maintaining a list of distinct numbers and their count. In find method we are iterating through distinct numbers and if value - num exist in hash, it means there is some number x in hash for which x + num = value so that's why we return True in that case.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.