Two Sum

# Two Sum ## Difficulty Easy ## Tags `array`, `hash table` ## Problem Statement Given an array of integers `nums` and an integer `target`, return the indices of the two numbers such that they add up to `target`. You may assume that each input has **exactly one solution**, and you may not use the same element twice. ## Constraints - 2 ≤ nums.length ≤ 10⁴ - -10⁹ ≤ nums[i] ≤ 10⁹ - -10⁹ ≤ target ≤ 10⁹ - Only one valid answer exists. - Return the answer in any order. ## Signatures ### Python ```python def two_sum(nums: List[int], target: int) -> List[int]: pass ``` ### Java ```java public class Solution { public List<Integer> two_sum(List<Integer> nums, int target) { return null; } } ``` ### Csharp ```csharp public class Solution { public IList<int> two_sum(IList<int> nums, int target) { throw new NotImplementedException(); } } ``` ### Cpp ```cpp class Solution { public: vector<int> two_sum(vector<int> nums, int target) { } }; ``` ### C ```c int* two_sum(int* nums, int target) { } ``` ### Ruby ```ruby def two_sum(nums, target) end ``` ### Perl ```perl sub two_sum { my ($self, @args) = @_; } ``` ### Scala ```scala object Solution { def two_sum(nums: List[Int], target: Int): List[Int] = { } } ``` ### Haskell ```haskell two_sum :: ... -> ... two_sum args = undefined ``` ### Clojure ```clojure (defn two_sum [nums target] ) ``` ### Scheme ```scheme (define (two_sum nums target) ) ``` ## Examples ### Example 1 **Input:** ``` nums = [2, 7, 11, 15] target = 9 ``` **Output:** ``` [0, 1] ``` **Explanation:** nums[0] + nums[1] = 2 + 7 = 9. ### Example 2 **Input:** ``` nums = [3, 2, 4] target = 6 ``` **Output:** ``` [1, 2] ``` **Explanation:** nums[1] + nums[2] = 2 + 4 = 6. ### Example 3 **Input:** ``` nums = [3, 3] target = 6 ``` **Output:** ``` [0, 1] ``` **Explanation:** nums[0] + nums[1] = 3 + 3 = 6. ## Hints 1. A brute force approach checks all pairs in O(N²). 2. Use a hash map to store elements you've already seen. 3. For each element, check if `target - element` exists in the hash map. 4. This achieves O(N) time complexity.