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 - Solution 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()

/** 0001.1 - Two Sum - Solution 1 - Brute Force */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums, target) {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] === target) {
                    return [i, j];
                }
            }
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0001.1 - Two Sum - Solution 1 - Brute Force */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums: number[], target: number): number[] {
        for (let i = 0; i < nums.length; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] === target) {
                    return [i, j];
                }
            }
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0001.1 - Two Sum - Solution 1 - Brute Force

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i]+nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return []int{}
}

func testcase() {
    // Test Function
    fmt.Println(twoSum([]int{3, 3}, 6))
    fmt.Println(twoSum([]int{3, 2, 4}, 6))
    fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
    testcase()
}

// 0001.1 - Two Sum - Solution 1 - Brute Force

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
struct Solution;

/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl Solution {
    /// Two Sum Function
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for i in 0..nums.len() {
            for j in (i + 1)..nums.len() {
                if nums[i] + nums[j] == target {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![]
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
fn testcase() {
    // Test Function
    println!("{:?}", Solution::two_sum(vec![3, 3], 6));
    println!("{:?}", Solution::two_sum(vec![3, 2, 4], 6));
    println!("{:?}", Solution::two_sum(vec![2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
fn main() {
    testcase();
}

Solution 2 - Brute Force - 2

TimeComplexity: O(n^2)

SpaceComplexity: O(1)

""" 0001.2 - Two Sum - Solution 2 - Brute Force using enumerate() """
"""Same brute-force logic, but uses Python's enumerate() for cleaner index tracking. The other languages use their idiomatic indexed-iteration equivalents."""

#####################################################################################
# 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):
                if num1 + num2 == target:
                    return [key1, key2]
        return []


#####################################################################################
# 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.2 - Two Sum - Solution 2 - Indexed Iteration */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums, target) {
        for (const [i, num1] of nums.entries()) {
            for (const [offset, num2] of nums.slice(i + 1).entries()) {
                const j = i + 1 + offset;
                if (num1 + num2 === target) {
                    return [i, j];
                }
            }
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0001.2 - Two Sum - Solution 2 - Indexed Iteration */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums: number[], target: number): number[] {
        for (const [i, num1] of nums.entries()) {
            for (const [offset, num2] of nums.slice(i + 1).entries()) {
                const j = i + 1 + offset;
                if (num1 + num2 === target) {
                    return [i, j];
                }
            }
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0001.2 - Two Sum - Solution 2 - Range Iteration

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func twoSum(nums []int, target int) []int {
    for i, num1 := range nums {
        for offset, num2 := range nums[i+1:] {
            j := i + 1 + offset
            if num1+num2 == target {
                return []int{i, j}
            }
        }
    }
    return []int{}
}

func testcase() {
    // Test Function
    fmt.Println(twoSum([]int{3, 3}, 6))
    fmt.Println(twoSum([]int{3, 2, 4}, 6))
    fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
    testcase()
}

// 0001.2 - Two Sum - Solution 2 - Iterator Enumeration

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
struct Solution;

/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl Solution {
    /// Two Sum Function
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        for (i, &num1) in nums.iter().enumerate() {
            for (j, &num2) in nums.iter().enumerate().skip(i + 1) {
                if num1 + num2 == target {
                    return vec![i as i32, j as i32];
                }
            }
        }
        vec![]
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
fn testcase() {
    // Test Function
    println!("{:?}", Solution::two_sum(vec![3, 3], 6));
    println!("{:?}", Solution::two_sum(vec![3, 2, 4], 6));
    println!("{:?}", Solution::two_sum(vec![2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
fn main() {
    testcase();
}

Solution 3 - Two-Pass Hash Table

Build a hash table in the first pass, then search for each number's complement in the second pass. The index check prevents reusing the same element twice.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0001.3 - Two Sum - Solution 3 - Two-Pass Hash Map """

#####################################################################################
# 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]
        return []


#####################################################################################
# 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.3 - Two Sum - Solution 3 - Two-Pass Hash Map */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums, target) {
        const indexByValue = new Map();
        nums.forEach((num, index) => indexByValue.set(num, index));

        for (let i = 0; i < nums.length; i++) {
            const j = indexByValue.get(target - nums[i]);
            if (j !== undefined && j !== i) {
                return [j, i];
            }
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0001.3 - Two Sum - Solution 3 - Two-Pass Hash Map */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums: number[], target: number): number[] {
        const indexByValue = new Map<number, number>();
        nums.forEach((num, index) => indexByValue.set(num, index));

        for (let i = 0; i < nums.length; i++) {
            const j = indexByValue.get(target - nums[i]);
            if (j !== undefined && j !== i) {
                return [j, i];
            }
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0001.3 - Two Sum - Solution 3 - Two-Pass Hash Map

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func twoSum(nums []int, target int) []int {
    indexByValue := make(map[int]int)
    for i, num := range nums {
        indexByValue[num] = i
    }

    for i, num := range nums {
        if j, found := indexByValue[target-num]; found && j != i {
            return []int{j, i}
        }
    }
    return []int{}
}

func testcase() {
    // Test Function
    fmt.Println(twoSum([]int{3, 3}, 6))
    fmt.Println(twoSum([]int{3, 2, 4}, 6))
    fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
    testcase()
}

// 0001.3 - Two Sum - Solution 3 - Two-Pass Hash Map

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
use std::collections::HashMap;

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
struct Solution;

/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl Solution {
    /// Two Sum Function
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut index_by_value = HashMap::new();
        for (i, &num) in nums.iter().enumerate() {
            index_by_value.insert(num, i);
        }

        for (i, &num) in nums.iter().enumerate() {
            if let Some(&j) = index_by_value.get(&(target - num)) {
                if j != i {
                    return vec![j as i32, i as i32];
                }
            }
        }
        vec![]
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
fn testcase() {
    // Test Function
    println!("{:?}", Solution::two_sum(vec![3, 3], 6));
    println!("{:?}", Solution::two_sum(vec![3, 2, 4], 6));
    println!("{:?}", Solution::two_sum(vec![2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
fn main() {
    testcase();
}

Solution 4 - One-Pass Hash Table

Build the hash table while searching. For each number, check whether its complement was seen earlier; if so, return both indices immediately.

TimeComplexity: O(n)

SpaceComplexity: O(n)

""" 0001.4 - Two Sum - Solution 4 - One-Pass Hash Map """

#####################################################################################
# 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 [hashmap[complement], key]
            hashmap[num] = key
        return []


#####################################################################################
# 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.4 - Two Sum - Solution 4 - One-Pass Hash Map */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums, target) {
        const indexByValue = new Map();
        for (let i = 0; i < nums.length; i++) {
            const complement = target - nums[i];
            if (indexByValue.has(complement)) {
                return [indexByValue.get(complement), i];
            }
            indexByValue.set(nums[i], i);
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase() {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

/** 0001.4 - Two Sum - Solution 4 - One-Pass Hash Map */

/////////////////////////////////////////////////////////////////////////////////////
// Classes
/////////////////////////////////////////////////////////////////////////////////////
class Solution {
    /** Two Sum Function */
    twoSum(nums: number[], target: number): number[] {
        const indexByValue = new Map<number, number>();
        for (let i = 0; i < nums.length; i++) {
            const complement = target - nums[i];
            const j = indexByValue.get(complement);
            if (j !== undefined) {
                return [j, i];
            }
            indexByValue.set(nums[i], i);
        }
        return [];
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
function testcase(): void {
    /** Test Function */
    const solution = new Solution();
    console.log(solution.twoSum([3, 3], 6));
    console.log(solution.twoSum([3, 2, 4], 6));
    console.log(solution.twoSum([2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
testcase();

// 0001.4 - Two Sum - Solution 4 - One-Pass Hash Map

package main

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
import "fmt"

/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
func twoSum(nums []int, target int) []int {
    indexByValue := make(map[int]int)
    for i, num := range nums {
        if j, found := indexByValue[target-num]; found {
            return []int{j, i}
        }
        indexByValue[num] = i
    }
    return []int{}
}

func testcase() {
    // Test Function
    fmt.Println(twoSum([]int{3, 3}, 6))
    fmt.Println(twoSum([]int{3, 2, 4}, 6))
    fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
func main() {
    testcase()
}

// 0001.4 - Two Sum - Solution 4 - One-Pass Hash Map

/////////////////////////////////////////////////////////////////////////////////////
// Imports
/////////////////////////////////////////////////////////////////////////////////////
use std::collections::HashMap;

/////////////////////////////////////////////////////////////////////////////////////
// Structs
/////////////////////////////////////////////////////////////////////////////////////
struct Solution;

/////////////////////////////////////////////////////////////////////////////////////
// Implementations
/////////////////////////////////////////////////////////////////////////////////////
impl Solution {
    /// Two Sum Function
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut index_by_value = HashMap::new();
        for (i, &num) in nums.iter().enumerate() {
            if let Some(&j) = index_by_value.get(&(target - num)) {
                return vec![j as i32, i as i32];
            }
            index_by_value.insert(num, i);
        }
        vec![]
    }
}


/////////////////////////////////////////////////////////////////////////////////////
// Functions
/////////////////////////////////////////////////////////////////////////////////////
fn testcase() {
    // Test Function
    println!("{:?}", Solution::two_sum(vec![3, 3], 6));
    println!("{:?}", Solution::two_sum(vec![3, 2, 4], 6));
    println!("{:?}", Solution::two_sum(vec![2, 7, 11, 15], 9));
}


/////////////////////////////////////////////////////////////////////////////////////
// Main
/////////////////////////////////////////////////////////////////////////////////////
fn main() {
    testcase();
}

0001 - Two Sum

Solution 1 : Brute Force

Solution 2 - Brute Force - 2

Solution 3 - Two-Pass Hash Table

Solution 4 - One-Pass Hash Table