Two Sum Problem

[Question] : Given an array of integers `nums` and an integer `target`, find indices of the two numbers which addition equals to target.
Example: Input: nums = [2,7,11,15], target = 13 Output: [0,2] Explanation: Because nums[0] + nums[2] == 13, we return [0, 2].

Approach #1 : Using Two pointers: –

Step 1: First sort array then
Step 2: If arr[left] + arr[right] > sum, we will decrement the right pointer.
Step 3: If arr[left] + arr[right] < sum, we will increment the left pointer.
Step 4: if arr[left] + arr[right] == sum, we will return the result.

``````// TC: O(N)
// SC: O(1)
func twoSum(arr: inout [Int], target: Int) ->[Int] {
arr.sort()
var left = 0
var right = arr.count - 1
while (left < right) {
let sum = arr[left] + arr[right]
if (sum == target) {
return [left, right]
} else if sum < target {
left+=1
} else {
right-=1
}
}
return []
}

var twoSumArr = [2, 6, 5, 8, 11]
let target = 14
let ans = twoSum(arr: &twoSumArr, target: target)
print("two sum index found-->", ans, twoSumArr[ans[0]], twoSumArr[ans[1]])``````
Approach#2 : Using Map/Dictionary

Since dictionary contains Unique keys we are storing elements to dictionary & when target-element is sum we are returning index.

``````func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var dictionary = [Int:Int]()
for (i, n) in nums.enumerated() {
if let last = dictionary[target - n] {
return [last, i]
}
dictionary[n] = i
}
return []
}``````