Two Sum III - Data structure design

You can design the TwoSum class using a dictionary to store the numbers and their counts. This structure will allow you to add numbers and find pairs with the desired sum efficiently.

Here’s the implementation:

1. Constructor (__init__): Initializes the dictionary to store the numbers.
2. add Method: Adds the given number to the dictionary. If the number is already present, increments its count.
3. find Method: Iterates through the dictionary, checking if there exists a pair of numbers that sum up to the given value. Returns true if found, false otherwise.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class TwoSum:
    def __init__(self):
        self.numbers = {}

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

    def find(self, value: int) -> bool:
        for num in self.numbers:
            complement = value - num
            if complement in self.numbers:
                if complement == num and self.numbers[complement] < 2:
                    continue
                return True
        return False

Explanation:

• add adds the number to the dictionary and increments the count if the number is already present.
• find looks for a pair that sums up to the given value. If the complement is the same as the current number, it checks if the count is greater than 1 to ensure that there are two instances of that number.

This implementation ensures that the constraints are met and provides an efficient way to add numbers and find pairs with the desired sum.