{x}
blog image

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 <= 104
  • -109 <= nums[i] <= 109
  • -109 <= target <= 109
  • Only one valid answer exists.

 

Follow-up: Can you come up with an algorithm that is less than O(n2) time complexity?

Solution Explanation: Two Sum

The problem asks to find two indices in a given array nums whose corresponding elements sum up to a given target. The challenge lies in doing this efficiently, aiming for better than O(n²) time complexity.

Approach: Hash Table (Optimal)

The most efficient solution leverages a hash table (or dictionary in Python) to achieve O(n) time complexity. Here's how it works:

  1. Initialization: Create an empty hash table (e.g., d in the Python code). This table will store each number from nums as a key, and its index as the value.

  2. Iteration: Iterate through the nums array. For each element x at index i:

    • Lookup: Check if target - x (let's call this y) exists as a key in the hash table d. If y is found, it means we've found a pair that sums to the target. The indices are the value associated with y (the index of y in nums) and the current index i. Return these indices.

    • Insertion: If y is not found in d, insert x and its index i into the hash table. This ensures that if we encounter y later, we can quickly find its index.

  3. No Solution: If the loop completes without finding a pair, it means no two numbers in nums sum to target. (The problem statement guarantees a solution exists, so this case might not need explicit handling in some implementations)

Time and Space Complexity Analysis

  • Time Complexity: O(n). We iterate through the nums array once. Hash table lookups and insertions are typically O(1) on average.

  • Space Complexity: O(n). In the worst case, the hash table could store all elements of nums.

Code Examples (Multiple Languages)

The provided code snippets demonstrate this hash table approach in several programming languages. Each version follows the same basic algorithm:

  • Python: Uses a dictionary for the hash table. The if (y := target - x) in d: line is a concise way to check for the presence of y and assign it to y simultaneously in a single expression.

  • Java, C++, Go, TypeScript, Rust, JavaScript, C#, PHP, Scala, Swift, Ruby, Kotlin, Nim, Cangjie: These all use their respective hash table implementations (HashMap, unordered_map, etc.) to efficiently store and retrieve elements and their indices. Minor syntax differences exist, but the underlying algorithm is the same.

All the code snippets effectively implement the same hash table-based solution, achieving optimal time complexity. The choice of language affects only the specific syntax and data structure used, not the core algorithm's efficiency.