Finding indices of array elements that add up to a target number. What would be a way to optimize my solution?

Question

I'm practicing this problem

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.

and came up with

class Solution {
    func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
        var indices = [Int]()
        
        for (firstIndex, firstNum) in nums.enumerated() {
            for (secondIndex, secondNum) in nums.enumerated() {
                if firstNum + secondNum == target && firstIndex != secondIndex {
                    indices = [firstIndex, secondIndex]
                }
            }
        }
        
        return indices
    }
}

However, it has quadratic time complexity because of the nested for-in loops. What would be a good way to optimize this to run in linear time?

Answer 1

Here's an idea that results in a O(n) time ans space solution.

1. Have a hashtable that maps elements to their indices.
2. As you iterate through the input array check whether target - element is in the hashtable already. If so, return the indices of the current element and target - element in the hashtable.
3. If not, add current element as key and its index as value to the hashtable.