Problem difficulty: Easy
Problem description
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]
Solution Approach
We are given an array and we need to find two elements that add up to the target sum. I will show you the brute force way (O(N^2)) and the more efficient way (O(N)).
O(N^2) Solution
To find the target sum using brute force, we can iterate through the array using nested loops. These loops will add each element to every other element, checking if the sum matches the target. Here’s the code
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
return [i, j]
return []
O(N) Solution
This solution leverages the power of a hash table. Since accessing elements in a hash table has a time complexity of O(1), we iterate through the array and store each element in the hash table with the element itself as the key and its index as the value. Then, for each element array[i], we check if the complement (target – array[i]), denoted by B, exists in the hash table. If it does, we’ve found a pair that sums up to the target and can return the result.
from typing import List
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_to_index = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
return [num_to_index[complement], i]
num_to_index[num] = i
return []
Source Code: https://github.com/hongquan080799/leetcode/tree/master/two_sum
