In this post, we are going to solve the 1. Two Sum – Leetcode Solution problem of Leetcode. This problem 1. Two Sum – Leetcode Solution is a Leetcode easy level problem. Let’s see the code, 1. Two Sum – Leetcode Solution – Leetcode Solution.

Problem

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⁴
• -10⁹ <= nums[i] <= 10⁹
• -10⁹ <= target <= 10⁹
• Only one valid answer exists.

Now, let’s see the leetcode solution of 1. Two Sum – Leetcode Solution.

Two Sum – Leetcode Solution

We are going to solve the problem using Priority Queue or Heap Data structure ( Max Heap ). Let’s see the solution.

1. Two Sum – Solution in Java

This is an O(N) complexity solution.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            int t = target - nums[i];
            if (map.containsKey(t)) {
                return new int[] {map.get(t), i};
            }
            map.put(nums[i], i);
        }
    }
}

This is an O(N^2) complexity solution.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
        	for (int j = i + 1; j < nums.length; j++) {
        		if (nums[i] + nums[j] == target) {
        			return new int[] {i, j};
        		}
        	}
        }
    }
}

1. Two Sum – Solution in C++

This is an O(N) complexity solution.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        map<int, int> d;
        for (int i = 0; i < nums.size(); i++) {
            int t = target - nums[i];
            if (d.find(t) != d.end()) {
                ans.push_back(d[t]);
                ans.push_back(i);
                break;
            }
            d[nums[i]] = i;
        }
        return ans;
    }
};

This is an O(N^2) complexity solution.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ans;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] + nums[j] == target) {
                    ans.push_back(i);
                    ans.push_back(j);
                    break;
                }
            }
        }
        return ans;
    }
};

1. Two Sum – Solution in Python

This is an O(N) complexity solution.

class Solution(object):
    def twoSum(self, nums, target):
        d = {}
        for i, num in enumerate(nums):
            t = target - num
            if t in d:
                return [d[t], i]
            d[num] = i
        return []

This is an O(N^2) complexity solution.

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

Note: This problem 1. Two Sum is generated by Leetcode but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.