У меня есть следующее решение этой проблемы. Временная сложность должна быть O (N), потому что операции HashMap put, get и keySet имеют значение O (1).
import java.util.HashMap;
import java.util.Map;
/**
* Find a pair of numbers in an array given a target sum
*
*
*/
public class FindNums {
public static void findSumsForTarget(int[] input, int target)
{
// just print it instead of returning
Map<Integer, String> myMap = populateMap(input);
// iterate over key set
for (Integer currKey : myMap.keySet()) {
// find the diff
Integer diff = target - currKey;
// check if diff exists in the map
String diffMapValue = myMap.get(diff);
if(diffMapValue!=null)
{
// sum exists
String output = "Sum of parts for target " + target + " are " + currKey + " and " + diff;
System.out.println(output);
return; // exit; we're done - unless we wanted all the possible pairs and permutations
}
// else
// keep looking
}
System.out.println("No matches found!");
}
private static Map<Integer, String> populateMap(int[] input)
{
Map<Integer,String> myMap = new HashMap<Integer,String>();
for (int i = 0; i < input.length; i++) {
String currInputVal = myMap.get(input[i]);
if(currInputVal!=null) // value already exists
{
// append current index location to value
currInputVal = currInputVal + ", " + i;
// do a put with the updated value
myMap.put(input[i], currInputVal);
}
else
{
myMap.put(input[i], Integer.toString(i)); // first argument is autoboxed to Integer class
}
}
return myMap;
}
// test it out!
public static void main(String[] args)
{
int[] input1 = {2,3,8,12,1,4,7,3,8,22};
int[] input2 = {1,2,3,4,5,6,7,8,9,10};
int[] input3 = {2,-3,8,12,1,4,7,3,8,22};
int target1 = 19;
int target2 = 16;
// test
FindNums.findSumsForTarget(input1, target1);
FindNums.findSumsForTarget(input1, -1);
FindNums.findSumsForTarget(input2, target2);
FindNums.findSumsForTarget(input3, target1);
}
}