This content originally appeared on DEV Community and was authored by Neeraj Kumar
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.
This content originally appeared on DEV Community and was authored by Neeraj Kumar
Neeraj Kumar | Sciencx (2024-11-12T18:20:38+00:00) Two Sum Problem’ on LeetCode. Retrieved from https://www.scien.cx/2024/11/12/two-sum-problem-on-leetcode/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.