Two Sum - Python Solution

1. Introduction

The "Two Sum" problem is a fundamental challenge in array manipulation and hash table usage. It's a common question in coding interviews and competitive programming. The problem involves finding two numbers in an array that add up to a given target sum. This task is crucial for understanding efficient data structure usage for lookups and array processing.

Problem

Given an array of integers nums and an integer target, the task is to return the indices of the two numbers in the array that add up to target. It is assumed that there is exactly one solution, and the same element cannot be used twice. The answer can be returned in any order.

2. Solution Steps

1. Use a hash table (dictionary in Python) to store the difference of the target and each element, along with the element's index.

2. Iterate through the array of numbers.

3. For each number, check if the number is in the hash table. If it is, return the current index and the stored index from the hash table.

4. If the number is not in the hash table, calculate the difference between the target and the current number, and store it in the hash table along with the current index.

5. Continue until a pair is found or the array is fully traversed.

3. Code Program

def twoSum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        if num in seen:
            return [seen[num], i]
        seen[target - num] = i

# Example Usage
print(twoSum([2, 7, 11, 15], 9))
print(twoSum([3, 2, 4], 6))
print(twoSum([3, 3], 6))

Output:

[0, 1]
[1, 2]
[0, 1]

Explanation:

1. Hash Table Usage: A hash table (seen) is used for storing the required complement of each number to reach the target.

2. Iterative Checking: As the array is iterated through, each number is checked against the hash table.

3. Pair Finding: If the current number is found in seen, it means the required pair has been identified.

4. Complement Storing: For numbers not found in seen, their complement (target - current number) is stored with their index.

5. Efficient Lookup: This approach allows for constant-time lookups, making the solution efficient.

6. Result: The function returns the indices of the two numbers that add up to the target.