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]

Constraints:

2 <= nums.length <= 104

• -10\(^{9}\) <= nums[i] <= 10\(^{9}\)
• -10\(^{9}\) <= target <= 10\(^{9}\)
• Only one valid answer exists.

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

Solution:

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        hash_table = {}
        for i, num in enumerate(nums):
          complement = target - num
          if complement in hash_table and hash_table[complement] != i:
            return [hash_table[complement], i]
          hash_table[num] = i
        return None
        

Time Complexity: The time complexity of the algorithm is O(n), where n is the length of the input array. This is because we are iterating through the array only once and performing constant time operations for each element. The hash table lookup operations and insertion operations both take constant time on average.

Space Complexity: The space complexity of the algorithm is O(n), where n is the length of the input array. This is because in the worst case, we may need to store all n elements of the array in the hash table. In practice, the space complexity will likely be less than O(n), since we will exit the function early once we find a solution, and we will not need to store all elements in the hash table.