Python without TLE (assuming add heavy)


  • 0
    A

    Assume add heavy

    1. Use dict(number:count) instead of raw number list to avoid too many repetitive numbers.
    2. Different from
      1. Two Sum (https://leetcode.com/problems/two-sum/) where numbers are stored in a list
        We store numbers in a dict, access time is O(1).

    '''
    class TwoSum(object):

    def __init__(self):
        """
        initialize your data structure here
        """
        self.number_count = dict()
    
        
    
    def add(self, number):
        """
        Add the number to an internal data structure.
        :rtype: nothing
        """
        number_count = self.number_count
        number_count[number] = number_count.get(number, 0) + 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
        """
        number_count = self.number_count
    
        for number, count in number_count.iteritems():
            other_number = value - number
            if other_number == number:
                if number_count[number] > 1:
                    return True
            else:
                if other_number in number_count:
                    return True
        return False
    

    '''


  • 0
    A

    If you use like

    for number in number_count.keys():
    `````
    It will out of time.


  • 0
    A

    @airflyctl Thanks. I find it a bit weird that TIME LIMIT ERROR occurs if find heavy is assumed:

    Assuming find heavy [CURRENT SOLUTION IS TIME LIMIT ERROR]: 
    1. Use set to store num.
    2. Compute possible sum and save in extra sum set every time we add.
    CARE: in add, update sums before update numbers (corner case: add(0); find(0))
    
    
    class TwoSum(object):
    
        def __init__(self):
            """
            initialize your data structure here
            """
            self.numbers = set()
            self.sums = set()
            
    
        def add(self, number):
            """
            Add the number to an internal data structure.
            :rtype: nothing
            """
            if number in self.numbers:
                self.sums.add(number * 2)
            else:
                for other_number in self.numbers:
                    self.sums.add(number + other_number)
                self.numbers.add(number)
            
    
        def find(self, value):
            """
            Find if there exists any pair of numbers which sum is equal to the value.
            :type value: int
            :rtype: bool
            """
            return value in self.sums
    

  • 0

    You don't need to keep a count of occurences in your number_count, only "seen" and "seen more than once".

    class TwoSum(object):
        def __init__(self):
            self.d = []
            self.c = {}
    
        def add(self, number):
            self.d.append(number)
            if number in self.c:
                self.c[number] = True
                return
            self.c[number] = False
    
        def find(self, value):
            for v in self.d:
                if value - v in self.c:
                    if v<<1 == value and not self.c[v]: continue
                    return True
            return False
    

Log in to reply
 

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