LeetCode-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(n2) time complexity?

Solutions:

a.Brute force solution:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                if (nums[i] + nums[j]) == target:
                    return [i,j] 
        

b. Using HashMap

class Solution:
    # This function finds two numbers in the 'nums' list that add up to the 'target' value.
    # It returns a list containing the indices of the two numbers.
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # Initialize an empty hashmap to store the values and their corresponding indices
        hashmap = {}  
    
        # Iterate through the 'nums' list using indices
        for i in range(len(nums)):  
            # Calculate the complement of the current number
            complement = target - nums[i]  
            
            # If the complement exists in the hashmap
            if complement in hashmap:  
                # Return the indices of the complement and the current number
                return [hashmap[complement], i]  
            
            # Add the current number and its index to the hashmap
            hashmap[nums[i]] = i