Two Sum Problem

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);

}

}