Two Sum

1. Two Sum

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]

1. Using HashMap

To solve the problem of finding indices of two numbers in an array that add up to a given target, you can use a dictionary (hash map) to store the indices of the numbers as you iterate through the array. This allows you to efficiently check if the complement of the current number (i.e., target - current number) has been seen before. This approach ensures an O(n)O(n)O(n) time complexity where nnn is the number of elements in the array.

Swift Implementation:

Here’s a Swift implementation of the solution:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    var numToIndex = [Int: Int]()
    
    for (index, num) in nums.enumerated() {
        let complement = target - num
        if let complementIndex = numToIndex[complement] {
            return [complementIndex, index]
        }
        numToIndex[num] = index
    }
    
    // Since the problem guarantees exactly one solution, we do not need to handle the case where no solution is found.
    return []
}

// Example usage:
let nums = [2, 7, 11, 15]
let target = 9
let result = twoSum(nums, target)
print(result)  // Output: [0, 1]

Explanation:

1. Dictionary Initialization:
   • var numToIndex = [Int: Int]() initializes an empty dictionary to store the indices of numbers encountered in the array.
2. Iteration:
   • The for loop uses enumerated() to iterate through the array while keeping track of both the index and the value (num) of each element.
3. Complement Calculation:
   • For each element, calculate the complement as target - num.
4. Check for Complement:
   • Check if the complement exists in the dictionary (numToIndex). If it does, return the indices of the complement and the current element.
5. Store Current Element:
   • If the complement does not exist in the dictionary, store the current element and its index in the dictionary (numToIndex[num] = index).
6. Return:
   • Since the problem guarantees exactly one solution, we return the result as soon as we find the complement. There is no need for additional checks or handling of cases where no solution is found.

2. Using loop

If you want to solve the problem without using a hash map, you can use a two-pointer technique after sorting the array. This approach will have a time complexity of O(nlog⁡n)O(n \log n)O(nlogn) due to the sorting step, followed by O(n)O(n)O(n) for the two-pointer traversal, resulting in an overall time complexity of O(nlog⁡n)O(n \log n)O(nlogn).

Swift Implementation:

Here’s a Swift implementation using the two-pointer technique:

func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
    // Create an array of tuples (num, index) to keep track of the original indices
    let numsWithIndex = nums.enumerated().map { ($0.element, $0.offset) }
    
    // Sort the array by the first element of the tuples (the numbers)
    let sortedNumsWithIndex = numsWithIndex.sorted { $0.0 < $1.0 }
    
    // Initialize two pointers
    var left = 0
    var right = sortedNumsWithIndex.count - 1
    
    // Two-pointer approach
    while left < right {
        let leftValue = sortedNumsWithIndex[left].0
        let rightValue = sortedNumsWithIndex[right].0
        let currentSum = leftValue + rightValue
        
        if currentSum == target {
            return [sortedNumsWithIndex[left].1, sortedNumsWithIndex[right].1]
        } else if currentSum < target {
            left += 1
        } else {
            right -= 1
        }
    }
    
    // Since the problem guarantees exactly one solution, this return statement will never be reached.
    return []
}

// Example usage:
let nums = [2, 7, 11, 15]
let target = 9
let result = twoSum(nums, target)
print(result)  // Output: [0, 1]

Explanation:

1. Enumerate and Map:
   • Create an array of tuples numsWithIndex where each tuple contains the number and its original index: [(num, index)].
2. Sort:
   • Sort numsWithIndex based on the numbers (the first element of the tuple).
3. Two Pointers:
   • Initialize two pointers, left at the beginning (0) and right at the end of the array.
4. Traverse with Two Pointers:
   • Calculate the sum of the numbers at the left and right pointers.
   • If the sum is equal to the target, return the indices of these numbers.
   • If the sum is less than the target, increment the left pointer to increase the sum.
   • If the sum is greater than the target, decrement the right pointer to decrease the sum.
5. Return Result:
   • Since the problem guarantees exactly one solution, the function will always return the indices of the two numbers that add up to the target.

3. Using for loop

func twoSum(_ nums: [Int],_ target: Int) -> [[Int]] {
    var result = [[Int]]()
    for i in 0..<nums.count {
        let complement = target - nums[i]
        for j in i..<nums.count {
            if nums[j] == complement {
                if !result.contains([nums[i],nums[j]]) {
                    result.append([nums[i],nums[j]])
                }
            }
        }
    }
    
    return result
  }
let nums = [2,4, 7,5, 11, 15]
let target = 9
let result = twoSum(nums, target)
print(result)