Two sum

Brute Force

Time Complexity: O(n²)
Space Complexity: O(1)

package main

import "fmt"

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 nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println(result) // Output: [0,1]
}

Hash Map

Time Complexity: O(n)
Space Complexity: O(n)

package main

import "fmt"

func twoSum(nums []int, target int) []int {
    hashMap := make(map[int]int)

    for i, num := range nums {
        complement := target - num
        if index, found := hashMap[complement]; found {
            return []int{index, i}
        }
        hashMap[num] = i
    }
    return nil
}

func main() {
    nums := []int{2, 7, 11, 15}
    target := 9
    result := twoSum(nums, target)
    fmt.Println(result) // Output: [0,1]
}

Explanation

Brute Force: Uses nested loops to check all pairs, leading to O(n²) time complexity.
Hash Map: Stores values in a map to find complements efficiently, reducing time complexity to O(n).