Problem Informations

• Problem Index: 1
• Problem Link: Two Sum
• Topics: Array, Hash Table

Problem Description

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

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

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:

Input: nums = [3,3], target = 6
Output: [0,1]

Constraints:

• $2 \leq \text{nums.length} \leq 10^4$
• $-10^9 \leq \text{nums}[i] \leq 10^9$
• $-10^9 \leq \text{target} \leq 10^9$
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than $O(n^2)$ time complexity?

Intuition

The problem at hand is a classic example of the “Two Sum” problem, which entails finding two distinct elements in an array that sum up to a specified target value. Given the constraints that there will always be exactly one solution and elements cannot be reused, our initial thought revolves around systematically iterating through the array to identify pairs of numbers whose total equals the target. This suggests a straightforward approach that compares each number with every other number in the array to find a complementary pair.

Approach

The approach is implemented as follows:

1. Initialize Result Container: We start by defining a container (a vector named result) to store the indices of the two numbers that sum up to the target.

2. Iterate Through the Array: We use a loop to traverse the array from the first element to the second-to-last element. This accounts for selecting the first number of the pair.

3. Find the Complement: For each number at index i, we calculate its complement as target - nums[i]. This complement represents the value needed in conjunction with nums[i] to reach the target sum.

4. Search for the Complement: Using the find function from the standard library, we search for this complement within the subarray starting from index i + 1 to the end of the array. This ensures that we do not reuse the same element for both numbers in the pair as per the problem’s constraints.

5. Verify the Complement: If the complement is found, find will return its index, otherwise, it will return the end iterator of the array. We check if the index of the found complement is valid (i.e., not equal to the size of the array).

6. Store the Result and Terminate: Upon finding a valid complement, we store the indices i and complementIndex into the result vector and break the loop, as there is only one solution guaranteed by the problem’s constraints.

7. Return the Result: Finally, we return the result vector containing the indices of the two numbers that add up to the target.

This approach, although simple, operates effectively within the constraints since it directly implements the solution search by leveraging the find function. Moreover, it inherently respects the constraint of not using the same element twice and assumes exactly one valid solution exists.

Code

C++

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> result;
        
        // Iterate through the numbers in the array except the last one
        for (int i = 0; i < nums.size() - 1; i++) {
            // Find the index of the complement that, together with nums[i], adds up to the target
            int complementIndex = find(nums.begin() + i + 1, nums.end(), target - nums[i]) - nums.begin();
            
            // If a valid index is found, store the indices and break the loop
            if (complementIndex != nums.size()) {
                result.push_back(i);
                result.push_back(complementIndex);
                break; // We assume there is only one solution
            }
        }
        
        return result;
    }
};

Python

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        
        # Iterate through the numbers in the array except the last one
        for i in range(len(nums) - 1):
            # Find the index of the complement that, together with nums[i], adds up to the target
            complementIndex = nums.index(target - nums[i], i + 1)
            
            # If a valid index is found, store the indices and break the loop
            if complementIndex != len(nums):
                result.append(i)
                result.append(complementIndex)
                break  # We assume there is only one solution
        
        return result

Complexity

• Time complexity: $O(n^2)$

  The algorithm primarily consists of a single loop and an inner call to the find function within each iteration. This function find has a time complexity of $O(n)$ because it, in the worst case, may need to iterate through nearly all remaining elements in the vector nums to find the complement. Since the outer loop also iterates $O(n)$ times, the overall time complexity of the algorithm is $O(n) \times O(n) = O(n^2)$.

• Space complexity: $O(1)$

  The space complexity is $O(1)$ because the algorithm uses a constant amount of extra space. Although a vector result is used to store the indices, the size of this vector is constant (at most 2 elements, since only two indices are stored as per the problem’s requirement for one valid solution). Hence, the additional space does not scale with the input size and remains constant.