# Problem Statement

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]
``````

## Brute Force Solution

A straightforward approach is to try all pairs of indices `(i, j)` and check if `nums[i] + nums[j] == target`. This approacha has quadratic running time and uses constant extra space (not counting the space used by `output`).

## Hash Map Solution

An optimized approach is to store the numbers in a Hash Table which enables constant lookup time:

``````def twoSum(nums: List[int], target: int) -> List[int]:
seen = {}
for i, num in enumerate(nums):
if (complement := target - num) in seen:
return [i, seen[complement]]
seen[num] = i
return []
``````

The time and space complexity is both `O(n)`. Obviously the linear running time is optimal as a linear scan of `nums` is inevitable.

## Variant I: Data Structure Design

``````from collections import Counter

class TwoSum:
def __init__(self):
self.counts = Counter()

def add(self, number: int) -> None:
self.counts[number] += 1

def find(self, value: int) -> bool:
return any(
(complement := value - num) in self.counts and
(complement != num or count > 1)
for num, count in self.counts.items()
)
``````

## Variant II: Input is sorted.

When `nums` is sorted we can use two-pointers technique:

``````def twoSum(numbers: List[int], target: int) -> List[int]:
left, right = 0, len(numbers) - 1
while left < right:
if numbers[left] + numbers[right] < target:
left += 1
elif numbers[left] + numbers[right] > target:
right -= 1
else:
return [left + 1, right + 1]
``````

Time complexity: `O(n)`

Space complexity: `O(1)`

## Variant III: Less Than K

``````def twoSumLessThanK(nums: List[int], k: int) -> int:
nums.sort()
i, j = 0, len(nums) - 1
ans = -1
while i < j:
if (two_sum := nums[i] + nums[j]) >= k:
j -= 1
else:
ans = max(ans, two_sum)
i += 1
return ans
``````

Time complexity: `O(nlogn)`

Space complexity: `O(n)` – Python uses timsort which has worst case linear space complexity.

## Variant IV: Three Sum

``````def threeSum(nums: List[int]) -> List[List[int]]:
nums.sort()
result = []
for i, a in enumerate(nums):
if a > 0:
break
if i > 0 and a == nums[i-1]:
continue
for b, c in two_sum(nums, i+1, -a):
result.append([a, b, c])
return result

def two_sum(nums, start_index, target):
i, j = start_index, len(nums) - 1
while i < j:
x, y = nums[i], nums[j]
if i > start_index and nums[i-1] == x:
i += 1
continue
if x + y == target:
yield x, y
i += 1
j -= 1
elif x + y < target:
i += 1
else:
j -= 1
``````

Time Complexity: `O(n^2)`

Space Complexity: `O(n)`