# 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)``````