import java.util.List;
import java.util.ArrayList;
import java.util.Map;
import java.util.HashMap;
class Main {
public static void main(String[] args) {
/**
* Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
*
* Assumptions:
* - Each input has exactly one solution
* - Cannot use the same element twice
* - Return indices in any order
*
* Example:
*
* Input: nums = [3, 2, 4], target = 6
* Output: [1, 2] // because nums[1] + nums[2] = 2 + 4 = 6
*/
final int target = 6;
final int[] nums = {3, 2, 4};
// Alright! I have to find the indexes of the numbers from the array
// that combined are equals to the target number
// The first approach that comes to my mind is using nested loops, where the outter loop picks each
// number (numA) and the inner loop allows to sum up and check if the sum is equals to the target
// We can store the indexes found in this array
List<Integer> output = new ArrayList<>();
// This flag will allow stopping the process if the numbers were found
boolean numbersFound = false;
// This is not the efficient approach
for (int i = 0; i < nums.length; i++) {
int numA = nums[i];
for (int j = 0; j < nums.length; j++) {
if (i != j) {
int numB = nums[j];
// If they combined are equals to the target, then we stop the process setting the flag as true
if (numA + numB == target) {
output.add(i);
output.add(j);
numbersFound = true;
break;
}
}
}
// If we found the numbers then we stop the outer loop
if (numbersFound) {
break;
}
}
System.out.println(output);
output.clear();
// A better approach is storing the numbers and the indexes in a Map collectior
// Then we can calculate "remanent = target - currentNumber" and check if this number is in the
// Map collection. Otherwise, we put the number with its index in the collection.
// This will allow to traverse the array once
Map<Integer, Integer> numbersProcessed = new HashMap<>();
for (int k = 0; k < nums.length; k++) {
int currentNum = nums[k];
int remanent = target - currentNum;
if (numbersProcessed.containsKey(remanent)) {
output.add(numbersProcessed.get(remanent));
output.add(k);
} else {
numbersProcessed.put(currentNum, k);
}
}
System.out.println(output);
}
}
