Solution 1 : Brute Force

Iterate through every pair of numbers using two nested loops. For each pair, check if they sum to the target. Return the indices when a match is found.

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.1 - Two Sum - Approach 1 - Brute Force """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################


class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]


#####################################################################################
# Functions
#####################################################################################


def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 2 - Brute Force using `enumerate()`

Same brute force logic, but uses Python's enumerate() for cleaner index tracking instead of range(len(...))

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.2 - Two Sum - Approach 1 - Brute Force using enumerate() """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################


class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        for key1, num1 in enumerate(nums):
            for key2, num2 in enumerate(nums[key1 + 1 :], key1 + 1):
	              # enumerate(iterable, start=1) -> start value determines starting index
                # Printing value and key will output 1 i , 2 j, 3 k, 4 l 
                if num1 + num2 == target:
                    return [key1, key2]


#####################################################################################
# Functions
#####################################################################################


def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 3 - Two-pass Hash Table Approach

This approach optimizes the hash table method by combining the building and searching phases into a single pass. As we iterate through the array, for each element we calculate its complement (target - current number) and check if it already exists in the hash table. If found, we immediately return the indices. If not, we add the current element and its index to the hash table before moving to the next element. This eliminates the need for a second pass through the array.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0001.3 - Two Sum - Approach 1 - Two Pass Hashmap """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################


class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        hashmap = {}
        for key, num in enumerate(nums):
            hashmap[num] = key
        for key, num in enumerate(nums):
            complement = target - num
            if complement in hashmap and hashmap[complement] != key:
                return [hashmap[complement], key]


#####################################################################################
# Functions
#####################################################################################


def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

Solution 4 - One-pass Hash TableApproach

This is the most efficient solution that combines building the hash table and searching for the complement in a single pass. As we iterate through the array, we first check if the complement (target - current number) exists in the hash table. If it does, we've found our answer and return immediately. If not, we store the current number and its index in the hash table for future lookups.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0001.4 - Two Sum - Approach 1 - One Pass Hashmap """

#####################################################################################
# Imports
#####################################################################################
from typing import List

#####################################################################################
# Classes
#####################################################################################


class Solution:
    """Solution Class"""

    def twoSum(self, nums: List[int], target: int) -> List[int]:
        """Two Sum Function"""
        hashmap = {}

        for key,num in enumerate(nums):
            complement = target - num
            if complement in hashmap:
                return [key, hashmap[complement]]
            hashmap[num] = key


#####################################################################################
# Functions
#####################################################################################


def testcase():
    """Test Function"""
    print(Solution().twoSum([3, 3], 6))
    print(Solution().twoSum([3, 2, 4], 6))
    print(Solution().twoSum([2, 7, 11, 15], 9))


#####################################################################################
# Main
#####################################################################################
if __name__ == "__main__":
    testcase()

0001 - Two Sum

Solution 1 : Brute Force

Solution 2 - Brute Force using enumerate()

Solution 3 - Two-pass Hash Table Approach

Solution 4 - One-pass Hash TableApproach

Solution 2 - Brute Force using `enumerate()`