type
status
date
slug
summary
tags
category
icon
password
Problem Statement
Given an array of integers
nums and an integer target, return the indices i and j such that nums[i] + nums[j] == target and i != j.
You may assume that every input has exactly one pair of indices i and j that satisfy the condition.
Return the answer with the smaller index first.Examples
- Input:
nums = [3,4,5,6],target = 7
- Output:
[0,1]
- Explanation:
nums[0] + nums[1] == 7, so we return[0, 1].
- Input:
nums = [4,5,6],target = 10
- Output:
[0,2]
- Input:
nums = [5,5],target = 10
- Output:
[0,1]
Constraints
2 <= nums.length <= 1000
-10,000,000 <= nums[i] <= 10,000,000
-10,000,000 <= target <= 10,000,000
Solutions
1. Brute Force
Core Idea
The most straightforward approach is to check every possible pair of numbers in the array. We can use nested loops to iterate through each element
nums[i] and then check if any subsequent element nums[j] sums up to the target.Time Complexity: O(n²)
Space Complexity: O(1)
2. Sorting
Core Idea
This method involves sorting the array first while keeping track of the original indices. Then, we use two pointers, one at the beginning (
i) and one at the end (j) of the sorted array. If the sum of the elements at these pointers is less than the target, we increment i to get a larger sum. If it's greater, we decrement j for a smaller sum. This efficiently narrows down the search space.Time Complexity: O(nlogn)
Space Complexity: O(n)
3. Hash Map (Two Pass)
Core Idea
To improve the time complexity, we can use a hash map. In the first pass, we populate the hash map with each number and its index (
value -> index). In the second pass, we iterate through the array again. For each number n, we calculate its required complement, diff = target - n. We then check if diff exists in the hash map. If it does, and its index is not the same as the current index, we have found our pair.Time Complexity: O(n)
Space Complexity: O(n)
4. Hash Map (One Pass)
Core Idea
We can optimize the hash map approach by combining the two passes into one. As we iterate through the array, for each element
n, we first check if its complement (diff = target - n) is already in the hash map. If it is, we have found our solution and can return immediately. If not, we add the current number n and its index i to the map for future elements to check against.Time Complexity: O(n)
Space Complexity: O(n)
Comparison
Solution | Time Complexity | Space Complexity |
Brute Force | O(n²) | O(1) |
Sorting | O(nlogn) | O(n) |
Hash Map (Two Pass) | O(n) | O(n) |
Hash Map (One Pass) | O(n) | O(n) |
Best Practice
The One-Pass Hash Map solution is the most optimal for this problem. It achieves the best possible time complexity of O(n) by iterating through the array only once. The use of a hash map provides constant-time O(1) lookups for the complement, making it highly efficient. While it uses O(n) space, this trade-off is generally worthwhile for the significant improvement in speed over the brute-force and sorting approaches.