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 <= nums.length <= 104

-109 <= nums[i] <= 109

-109 <= target <= 109

Only one valid answer exists.

Solution 1

This brute force solution has some minor tweaks that marginally improve the performance, but it still has an exponential time complexity of O(n^2) and a constant space complexity of O(1).

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
  let n = nums.count
  for i in 0 ..< n {
    for j in i + 1 ..< n {
      if nums[i] + nums[j] == target {
        return [i,j]
      }
    }
  }
  return []
}

Follow-up

Can you come up with an algorithm that is less than O(n2) time complexity?

I had to look at the answer, and I initially found it very confusing primarily because the variable names were all very non-specific. That may be the culture on LeetCode, but for me properly named variables remove much of the cognitive load from reading the function.

This solution has a O(n) linear time and space complexity, an is relatively straightforward.

Solution 2

func twoSum(_ n: [Int], _ t: Int) -> [Int] {
  var viewed = [Int:Int]()
    for (index, number) in n.enumerated() {
        if let complement = viewed[t-number] {
            return [complement, index] 
        }
      viewed[number] = index
    }
  return []
}