Efficient Solutions to LeetCode Two Sum Problem: Hash Table Strategy and Python Implementation

Problem Background and Challenges

The Two Sum problem on LeetCode requires finding two numbers in an integer array such that their sum equals a given target value. The core challenge lies in designing an efficient algorithm to avoid the O(n²) time complexity from using double loops. In the original problem description, for an input array like {2, 7, 11, 15} and target 9, it should return indices index1=1, index2=2 (note the 1-based indexing).

Brute-Force Approach and Its Limitations

The most intuitive solution is to use two nested loops to traverse all possible pairs and check if their sum equals the target. Although simple, this method has a time complexity of O(n²), making it inefficient for large datasets. For example, implemented in Python as:

def twoSum_bruteforce(nums, target):
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            if nums[i] + nums[j] == target:
                return [i+1, j+1]  # Convert to 1-based indices

This approach often fails on LeetCode due to timeouts, especially with large arrays.

Hash Table Optimization Strategy

To improve efficiency, a hash table (dictionary in Python) can be used to reduce lookup time to O(1). The core idea is: for each element nums[i] in the array, compute the complement target - nums[i] and check if it exists in the hash table. If it does, a solution pair is found; otherwise, store the current element and its index in the hash table for future lookups.

Referring to the best answer (Answer 1), an efficient implementation is:

def twoSum_hashmap(nums, target):
    lookup = {}
    for i, v in enumerate(nums):
        complement = target - v
        if complement in lookup:
            return [lookup[complement] + 1, i + 1]  # Return 1-based indices
        lookup[v] = i

This algorithm traverses the array only once, with time complexity O(n) and space complexity O(n), as in the worst case, all elements need to be stored in the hash table.

Algorithm Details and Edge Cases

Several key points must be considered during implementation. First, the problem assumes exactly one solution per input, simplifying handling without needing to account for multiple solutions. Second, the 1-based indexing requirement can be met by adding 1 when returning indices. Additionally, if the array contains duplicate elements, such as [3, 3] with target 6, the algorithm should correctly return [1, 2]. The above implementation avoids using the same element twice by checking the complement before inserting the current element.

Another common optimization is using the enumerate function to obtain both index and value simultaneously, improving code readability. For example:

for index, value in enumerate(nums):
    # Processing logic

Comparison with Other Solutions

Referring to other answers, Answer 2 proposes a similar hash table approach but uses setdefault to maintain the lowest index, suitable for scenarios requiring the earliest occurrence. Answer 3 offers more concise code, directly using the in operator to check key existence, a common practice in real-world applications. Answer 4 emphasizes descriptive variable names and type hints to enhance code maintainability.

These variants are essentially based on the same hash table principle, with main differences in error handling, index management, and coding style. For instance, Answer 1 uses lookup.get(target-v, i) != i to ensure the same index is not returned, while Answer 3 avoids this by checking before insertion.

Practical Applications and Extensions

The Two Sum problem is not only a common interview question but also has real-world applications in caching systems, database indexing, and compiler optimizations. Understanding this problem helps in mastering more complex algorithms like Three Sum or Subarray Sum Equals K.

In Python, dictionary lookup operations have an average time complexity of O(1), but can degrade to O(n) in worst-case scenarios, though this rarely occurs in practice. For further optimization, sets or other data structures can be considered, but dictionaries are more suitable due to their key-value pair nature.

Conclusion

By analyzing the Two Sum problem, we demonstrate how to optimize from a brute-force solution to an efficient algorithm based on hash tables. Key points include: leveraging space-time trade-offs, correctly handling duplicate elements, and converting indices. The code examples provided in this article are refactored to clearly show core logic, aiding readers in deeply understanding algorithm design principles. Mastering this method lays a solid foundation for solving more complex algorithmic problems.