LeetCode 1. Two Sum

Description

https://leetcode.com/problems/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]
Output: 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 <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

Explanation

The question is about finding two elements in an array that they add up to a given target.

Simply, we can use a nested loop to solve. We can use a variable i to visit each element and use another variable j to check if there is another element in array add variable i value equal to target. The idea is easy. However, the solution is not efficient. The time complexity would be O(N²).

There is a better way to solve the problem. We can introduce a HashMap to reduce time complexity. The HashMap stores visited element values and indexes. Every time we visit an element, we store the element value and index into the HashMap, and we check if the current element’s complement already exists in the HashMap. If the complement exists, we find a solution. The solution is efficient. Time Complexity is O(N).

Java Solution

public class Solution {

  public int[] twoSum(int[] nums, int target) {
    int[] result = new int[2];

    Map<Integer, Integer> visited = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
      if (visited.containsKey(target - nums[i])) {
        result[0] = visited.get(target - nums[i]);
        result[1] = i;
        return result;
      }
      visited.put(nums[i], i);
    }

    return result;
  }
}

Python Solution

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        result = []
        visited = {}
        
        for i, num in enumerate(nums):
            complement = target - num
            
            if complement not in visited:    
                visited[num] = i
            else:
                result.append(i)
                result.append(visited[complement])
        
        return result

• Time Complexity: ~N
• Space Complexity: ~N