⚡Two Sums

#1. Two Sums

• Difficulty: Easy
• Company: LeetCode75
• Language: Python
• Optimization: Yes
• Review: December 22, 2024
• Select: Array, Hash Table
• Solved: Yes
• Tried:1

Description

• If the summary of the two elements of the nums array is the same as that of a target, return the index of the two elements.
• The nums array is guaranteed to contain two elements whose sum equals the given target.

My Answer: All possible cases

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

• Description:
  • The outer loop(i) iterates through all elements of the nums array in order
  • The inner loop(j) starts from i+1 and iterates through the rest of the elements, ensuring no duplicate pairs are checked.
  • The double-loop structure covers all possible pairs of two distinct elements(two elements subset) in the nums array.
  • If the sum of the two elements(nums[i]+nums[j]) equals the target, the function returns the indices([i,j])
• Time: O($N^2$)
  • The outer loop(i) depends on the length of the nums array → $O(n)$
  • The inner loop(j) repeats n-i-1 times on each $i$ term → $O$($N^2$)
• Space: O(1)
  • Only uses two variables, i and j, to track the indices → $O(1)$

Reflection

• Exploring various solutions and clearly communicating them
• Stating the runtime and space complexity (the pros and cons) of each solution)
• Translating ideas into code
• Debugging your code

Best Answer

1. Hash Table

class Solution:
	#nums = [2,7,11,15]
  def twoSum(self, nums: List[int], target: int) -> List[int]:
    indices = {num: idx for ***idx, num*** in enumerate(nums)}
     # Step 1: Create a dictionary (value: index) from nums
      # Example: {2: 0, 7: 1, 11: 2, 15: 3}

		# Step 2: Loop through nums using enumerate to get (index, value)
		# Example: {0:2, 1:7, 2:11, 3:15}
    for i, v in enumerate(nums):
      complement = target - v
      if complement in indices and indices[complement] != i:
       # Step 3: Check if a complement exists in the dictionary 
       #and avoid using the same index
        j = indices[complement]
        return [i, j]

• Description
  1. Create an indices object with (value: index) of a nums array.
     1. If nums = [2,7,5] , indices = {2: 0, 7: 1, 5: 2}
  2. Loop the enumerate(nums) object which has (index: value) of nums
     1. enumerate(nums) = {0: 2, 1: 7, 2: 5}
  3. if complement(target-v) is in the indices object and different with indices[target-v] and $i,$ be assigned to $j$
     • Find the complement(target-v) in the indices
     • If it is existed, find $j$ index of complement(target - num[i]
• Time: $O(n)$
  • If we know the dictionary’s key when searching, we can approach the value directly.
• Space: $O(n)$
  • The dictionary requires space proportional to the size of nums → $O(n)$
  • While we only use variables i and j within loop → $O(1)$
  • Total : $O(n) = O(n) + O(1)$