:orphan:

Two Sum
=======

.. highlight:: none

Problem
-------
https://leetcode.com/problems/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]



**Constraints:**

- ``2 <= nums.length <= 10``\ :sup:```4```
- ``-10``\ :sup:```9```\ ``<= nums[i] <= 10``\ :sup:```9```
- ``-10``\ :sup:```9```\ ``<= target <= 10``\ :sup:```9```
- **Only one valid answer exists.**



**Follow-up:**\ Can you come up with an algorithm that is less than
``O(n``\ :sup:```2```\ ``)`` time complexity?

.. highlight:: python

Pattern
-------
Array, Hash Table

Approaches
----------

.. tab-set::

    .. tab-item:: Two Pointer

        **Explanation**

        Pair each value with its original index, then sort by value. Set two
        pointers ``i`` and ``j`` to the beginning and end of the sorted list. If
        ``nums[i] + nums[j]`` is less than ``target``, increase the sum by moving
        ``i`` right; if greater, decrease the sum by moving ``j`` left. Stop when
        the sum equals ``target`` and return the two original indices.

        **Code**

        .. literalinclude:: ../problems/easy/two-sum/two_sum__two_pointer.py
            :language: python
            :lines: 11-

        **Test**

        >>> from two_sum__two_pointer import twoSum
        >>> twoSum([2,7,11,15], 9)
        [0, 1]
        >>> twoSum([3,2,4], 6)
        [1, 2]
        >>> twoSum([3, 3], 6)
        [0, 1]

        **Complexity**

        | :math:`n` is the length of the input array.
        | Time: :math:`O(n \log n)` — dominated by the sort.
        | Auxiliary Space: :math:`O(n)` — the enumerated-and-sorted copy.

        .. autofunction:: two_sum__two_pointer.twoSum

    .. tab-item:: Hash Map

        **Explanation**

        Single pass: for each ``nums[i]``, check whether ``target - nums[i]`` is
        already present in a dict mapping previously-seen values to their indices.
        If so, the two indices form the answer; otherwise record ``nums[i]`` for
        later lookups.

        **Code**

        .. literalinclude:: ../problems/easy/two-sum/two_sum__hash_map.py
            :language: python
            :lines: 11-

        **Test**

        >>> from two_sum__hash_map import twoSum
        >>> twoSum([2, 7, 11, 15], 9)
        [0, 1]
        >>> twoSum([3, 2, 4], 6)
        [1, 2]
        >>> twoSum([3, 3], 6)
        [0, 1]

        **Complexity**

        | :math:`n` is the length of the input array.
        | Time: :math:`O(n)` — one pass with :math:`O(1)` average-case dict lookups.
        | Auxiliary Space: :math:`O(n)` — the dict stores at most :math:`n` entries.

        .. autofunction:: two_sum__hash_map.twoSum