Two Sum - LeetCode Solution and Approach

 1. Two Sum - LeetCode - Easy

Solve this problem in LeetCode

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]

 

Constraints:

2 <= nums.length <= 10^4

-10^9 <= nums[i] <= 10^9

-10^9 <= target <= 10^9

Only one valid answer exists.

Approach:

If we try to find sum of each 2 integers in array, we will have to iterate through array in nested way and ends up getting time complexity of 0(n^2).

Instead we can store the value of target-currentValue in Map.

As, anyUpcomingValue + currentValue = Target, so anyUpcomingValue = Target - currentValue

So if we found anyUpcomingValue equals to previously stored target-currentValue, we will get the pair. But we want indexes of those pairs, so we will store the index as value in Map.

JAVA:

Time Complexity : 0(n)

Space Complexity: 0(n)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map < Integer, Integer > map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) // if such pair found
                return new int[] {map.get(nums[i]), i}; // then return pair's indexes
            map.put(target - nums[i], i); // storing key as target-currentValue and value as currentIndex 
        }
        return new int[] {-1, -1}; // return [-1,-1] if no such pair found
    }
}

Keep Learning and Practicing with Programming Chaska !!!