Two Sum Problem' on LeetCode

Problem Description
Given an array of integers nums and an integer target, return the indices of the two numbers that add up to the target.

Go Function Signature:
func twoSum(nums []int, target int) []int
Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] nums[1] == 9, we return [0, 1].
Example 2:

Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3:

nput: nums = [3,3], target = 6
Output: [0,1]
Solution 1: Brute Force Approach

Solution 1: Brute-Force Approach (Nested Loops)
In this approach, you check each pair of elements to see if they sum up to the target. This involves iterating through the array with two nested loops.

Code

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
}

Complexity Analysis

Solution 2: Two-Pass Hash Table
This solution improves on the brute-force approach by using a hash map to store each element's value and index in the first pass. In the second pass, you check if the complement (i.e., target - num) exists in the hash map.

Code

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    // First pass: populate the map with each element's index
    for i, num := range nums {
        numMap[num] = i
    }
    // Second pass: check for the complement
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok && i != j {
            return []int{i, j}
        }
    }
    return nil
}

Solution 3: One-Pass Hash Table (Optimal Solution)

• This approach combines both insertion and lookup in a single pass. As you iterate through the array, you:

• Check if the complement (i.e., target - num) exists in the hash map.

• If the complement is found, return the indices.

• If not, add the current element and its index to the hash map for future lookups.
  Code
  

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}

Complexity Analysis

• Time Complexity: ?(?)

  • Only one pass through the array is required, making this approach linear in time complexity.

• Space Complexity:o(n)

  • The hash map stores each element and its index.

Pros and Cons
Pros: The most efficient approach for time complexity, with a clean and compact implementation.
Cons: None, as it achieves optimal time and space complexity for this problem.

The above is the detailed content of Two Sum Problem' on LeetCode. For more information, please follow other related articles on the PHP Chinese website!