Scribd
Upload
90 views2 pages

Two Sum Algorithm with Hash Table

The document describes the 'Two Sum' problem, which requires finding indices of two numbers in an array that add up to a given target. It provides examples and constraints, ensuring that each input has exactly one solution. A hash table solution is proposed to achieve efficient time complexity while traversing the array.

Uploaded by

Youssef Sbai idrissi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
90 views2 pages

Two Sum Algorithm with Hash Table

The document describes the 'Two Sum' problem, which requires finding indices of two numbers in an array that add up to a given target. It provides examples and constraints, ensuring that each input has exactly one solution. A hash table solution is proposed to achieve efficient time complexity while traversing the array.

Uploaded by

Youssef Sbai idrissi
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

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]
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(n ) time complexity?
2

Solutions

Solution 1: Hash Table

We can use the hash table to store the array value and the
corresponding subscript.

Traverse the array nums, when you find target - nums[i] in the hash
table, it means that the target value is found, and the index of target
- nums[i] and are returned.

The time complexity is and the space complexity is . Where is the


length of the array nums.

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
m = {}
for i, x in enumerate(nums):
y = target - x
if y in m:
return [m[y], i]
m[x] = i

You might also like