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 []
}