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