Objective
Given an array of integers and a value, find a pair of distinct elements in the array that sum to the given value.
Observations
- We want to find two elements satisfying:
element1 + element2 = value
- We need to find
element1
andelement2
within the array that satisfy the equation above (if they even exist), butvalue
is known. - We can rearrange this equation as:
element1 = value - element2
element2 = value - element1
Code
import java.util.*;
class Solution {
/**
* @param int[] nums An array of non-negative integers
* @param int sum The value the pair of elements must sum to
*
* @return The distinct pair of VALUES in the array whose corresponding
* values sum to the value of 'sum', or [-1, -1] if not found.
**/
public static int[] twoSumValues(int[] nums, int sum) {
// Create a map of num elements to indices
Map numToIndex = new HashMap();
// Fill the map
for (int i = 0; i < nums.length; i++) {
// It doesn't matter if indices are overwritten
// because the final value will map to the largest index
numToIndex.put(nums[i], i);
}
// Iterate through values from smallest index to largest
// This ensures that overwritten values still match to later indices
// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
for (int i = 0; i < nums.length - 1; i++) {
// See if a match exists in map
Integer index = numToIndex.get(sum - nums[i]);
// If match exists and the second element's index is later than the first
if (index != null && index > i) {
// Return the pair of distinct indices
return new int[]{nums[i], nums[index]};
}
}
// No solution found
return new int[]{-1, -1};
}
/**
* @param int[] nums An array of non-negative integers
* @param int sum The value
*
* @return The distinct pair of INDICES in the array whose corresponding
* values sum to the value of 'sum', or [-1, -1] if not found.
**/
public static int[] twoSumIndices(int[] nums, int sum) {
// Create a map of num elements to indices
Map numToIndex = new HashMap();
// Fill the map
for (int i = 0; i < nums.length; i++) {
// It doesn't matter if indices are overwritten
// because the final value will map to the largest index
numToIndex.put(nums[i], i);
}
// Iterate through values from smallest index to largest
// This ensures that overwritten values still match to later indices
// (e.g., if sum is 4 and there is a 2 at both indices 0 and 1, map only contains 2 mapped to 1)
for (int i = 0; i < nums.length - 1; i++) {
// See if a match exists in map
Integer index = numToIndex.get(sum - nums[i]);
// If match exists and the second element's index is later than the first
if (index != null && index > i) {
// Return the pair of distinct indices
return new int[]{i, index};
}
}
// No solution found
return new int[]{-1, -1};
}
}