Question 3
Question 3: 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]
Constraints:
2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]
Only one valid answer exists.
Alert: Can you come up with an algorithm that is less than O(n2) time complexity?
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]
Solution:
C++
Java
Python
C++
Run
#include <bits/stdc++.h>
using namespace std;
vector twoSum(vector& nums, int target) {
unordered_map<int, int=""> numToIndex;
vector result;
for (int i = 0; i < nums.size(); i++) {
int complement = target - nums[i];
if (numToIndex.find(complement) != numToIndex.end()) {
result.push_back(numToIndex[complement]);
result.push_back(i);
break;
}
numToIndex[nums[i]] = i;
}
return result;
}
int main() {
int n, target;
cout << "Enter the number of elements: "; cin >> n;
vector nums(n);
cout << "Enter the elements: ";
for (int i = 0; i < n; i++) { cin >> nums[i];
}
cout << "Enter the target sum: "; cin >> target;
vector indices = twoSum(nums, target);
cout << "Indices of two numbers that add up to target: " << indices[0] << " " << indices[1] << endl;
return 0;
}
Java
Run
import java.util.*;
class Main {
public static int[] twoSum(int[] nums, int target) {
Map numToIndex = new HashMap<>();
int[] result = new int[2];
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (numToIndex.containsKey(complement)) {
result[0] = numToIndex.get(complement);
result[1] = i;
break;
}
numToIndex.put(nums[i], i);
}
return result;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the number of elements: ");
int n = sc.nextInt();
int[] nums = new int[n];
System.out.print("Enter the elements: ");
for (int i = 0; i < n; i++) {
nums[i] = sc.nextInt();
}
System.out.print("Enter the target sum: ");
int target = sc.nextInt();
int[] indices = twoSum(nums, target);
System.out.println("Indices of two numbers that add up to target: " + indices[0] + " " + indices[1]);
}
}
Python
Run
def two_sum(nums, target):
num_to_index = {}
result = []
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_index:
result.append(num_to_index[complement])
result.append(i)
break
num_to_index[num] = i
return result
n = int(input("Enter the number of elements: "))
nums = list(map(int, input("Enter the elements: ").split()))
target = int(input("Enter the target sum: "))
indices = two_sum(nums, target)
print("Indices of two numbers that add up to target:", indices[0], indices[1])
