Two Sum
Problem: Given an array of integers
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.
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]
To solve this problem efficiently, you must use HashMap data structure because it makes it really easy to avoid duplication of data in HashMap. It automatically gets rid of duplicate keys and the problem clearly states that you can have Only one solution and can be in any order.
This problem can be solved by many ways, but here I would explain only one of the efficient ways to do so which is using HashMap data structure.For example,
Input : 3, 2 , 4 with Target T= 6
HashMap will store each value i.e. 3, 2, 4 as keys and their index as their value. So visual representation would be :
HashMap[3,0], [2,1], [4,2] = [Key (input), Value (index)]
Thus it makes it really easy to return index value for the answer when we want to display it.
For solution, you can easily predict the next number you need by simple substraction
If T=6, and input is [3,2,4], then so as you can see first item in the array is 3, then 2 and 4.
if you subtract 6-3 = 3
we already got 3, so now all we need is another 3, if we find it then we have found a pair of items that is total of 6 which is Target.
Step 1:
Initialize HashMap<int, int>
Then first element 3, so 6-3 = 3
(We need another 3 in array to find second pair that can have sum of 6)
Save Map[3,0]
Step 2:
6-2 = 4 (we need 4 value to return a pair index if there's any)
Step 3:
Does 4 exists in Map? So far we have Map[3,0] so No.
So, Save Map[2,1]
Step 4:
6-4=2 (We need 2 remaining to make up for T =6 n return pair)
Step 5:
Does 2 exists in Map? Answer is Yes. So far we have Map[3,0], [2,1]
Step 6:
Return current Index which is 2 (3rd element, index = 2) and index stored of Map[2,1] (value, index)
Step 7:
Answer is [1, 2]
These steps are done in the following code
vector<int> efficientTwoSum(vector<int> &nums, int target){
map<int, int> umap;
for(int i=0; i < nums.size(); i++){
if(umap.find(target - nums[i]) != umap.end()){
nums.resize(0);
nums.push_back(umap[target-nums[i]]); //umap[id] gives value
nums.push_back(i);
break;
//return nums;
}
else{
umap[nums[i]] = i; // value -> index
}
}
return nums;
}
Solution in C++
#include <iostream>
#include<vector>
#include<map>
#include <unordered_map>
using namespace std;
vector<int> nums;
class Solution{
public:
void printVector(vector<int> &v, string methodName){
cout << endl;
cout << methodName << "answer:";
for ( int x : v){
std::cout << x << ", ";
}
}
void printAnswerFormat(vector<int> &v){ //assuming only have to print two indexes
//for (int i =0; i < v.size(); i++){
cout << endl;
cout << "answer: element num = [" << v[0] << "," << v[1] << "]" << endl;
}
void printMap(map<int, int> &m){
cout << "Printing Map....";
cout << endl;
for (auto i : m){
cout << "key: " << i.first << " value: " << i.second << endl;
}
}
vector<int> efficientTwoSum(vector<int> &nums, int target){
//vector<int> answer;
map<int, int> umap;
for(int i=0; i < nums.size(); i++){
if(umap.find(target - nums[i]) != umap.end()){
nums.resize(0);
nums.push_back(umap[target-nums[i]]); //umap[id] gives value
nums.push_back(i);
break;
//return nums;
}
else{
umap[nums[i]] = i; // value -> index
// index - > value (of vector[i])
// ideally idex is unique which should be preferred to store as KEY
//, however, hashmap automatically removes duplicates key,
// so value would be fine as well.
// eg. 2 2 2 7 so hashmap won't store 2 - 0 , 2 - 1, 2 - 2
// instead it will remove duplicate and store the latest which is
// 2 -> 2, 7->3, if target is 9, then [2,3] is the answer
//hashmap also automatically sorts <int> keys into sorted order.
}
}
printMap(umap);
printVector(nums, "efficientTwoSum");
//printVector(nums);
printAnswerFormat(nums);
return nums;
}
vector<int> bruteForceTwoSum(vector<int> &nums, int target){
//printVector()
for(int i = 0; i <= nums.size(); i++){
if(nums[i] + nums[i+1]== target){
nums.resize(0);
nums.push_back(i);
nums.push_back(i+1);
break;
}
}
printVector(nums, "BruteForceTwoSum");
printAnswerFormat(nums);
return nums;
}
void bruteForceTwoSumUsingArray(){
int arraysize = 0;
int target =0;
std::cout<<"how many values in array?" << endl;
std::cin >> arraysize;
std::cout <<"target value?" <<endl;
std::cin >> target;
int array[arraysize-1]; //for example 6... array[6] = 0, 1, 2, 3, 4, 5
for(int i=0; i < arraysize; i++ ){
cout << "element=" << i << " ";
cin >> array[i];
}
std::cout << "Printing array" <<endl ;
for ( int i = 0; i < arraysize;i ++){
cout << array[i] << ",";
}
cout << endl;
for(int i = 0; i < arraysize; i++){
cout << array[i] << "and" << array[i+1] << endl;
if(array[i] + array[i+1] == target ){
cout << "answer:" << array[i] << "and " << array[i+1] <<endl;
cout << "answer: element num = [" << i << "," << i+1 << "]" << endl;
break;
}else{
//cout << "No target found";
}
}
}
};
int main(){
int sizeOfVector = 0;
std::cout << "Enter size of Vector: " << endl;
std::cin >> sizeOfVector;
int target= 0;
std::cout << "target value :" << endl;
std::cin >> target;
// in vector, don't use size-1 because size starts with 1
int input;
for(int i=0; i < sizeOfVector; i++){
std::cin >> input;
nums.push_back(input);
}
Solution mySolution;
mySolution.efficientTwoSum(nums, target);
mySolution.bruteForceTwoSum(nums, target);
return 0;
}
Solution in Kotlin
import java.util.Scanner
fun main(){
val scan = Scanner(System.`in`)
print("Enter array size: ")
var arraySize = scan.nextInt()
print("Enter ${arraySize} values: \n")
var array = IntArray(arraySize)
for(i in 0 until arraySize){
array[i] = scan.nextInt()
}
//Different ways to print items
// array.forEach(System.out::print) //to print all values without any delimiter
println(array.joinToString(",")) //to seperate items
val target:Int
print("Enter target Value:")
target = scan.nextInt()
//print("$target") //Just to print targt value
//Using Array
// array = twoSumUsingArray(array, target)
// println("[" + array.joinToString(",") + "]")
array = twoSumUsingHashMap(array, target)
println("TwoSum answer: "+"[" + array.joinToString(",") + "]")
}
fun twoSumUsingArray(array: IntArray, target:Int) : IntArray{
for(i in 0 until array.size){
for(j in i+1 until array.size){
if(array[i] + array[j] == target){
return intArrayOf(i,j)
}
}
}
return intArrayOf(0,0)
}
fun twoSumUsingHashMap(array: IntArray, target:Int) : IntArray{
val map = HashMap<Int, Int>()
array.forEachIndexed{
index, item ->
val found = map[target-item]
found?.let{
return intArrayOf(found, index)
}
map.put(item, index)
}
return intArrayOf(-1,-1)
}
fun twoSumwithPair(array: IntArray, target:Int) : Pair<Int, Int>{
val map = hashMapOf<Int, Int>()
array.forEachIndexed{
index, value ->
if(map.contains(target-value)){
return Pair(map[target-value]!!, index)
}
map.put(value, index)
}
return Pair(-1,-1)
}
Hope I have explained well, but also it requires you to be familiar with HashMap and basic programming terms and logic. If you have any question, feel free to comment. I would be happy to explain and/or answer any of your question. Happy coding.
0 Comments