I am trying to find a way to get the first 2 elements from a map which their value combined gives me a desired sum. I was thinking of a solution which combined 2 maps where the key of the second map is the reminder of the target number minus the value of the entry of the first map. I am lost and not sure what I am missing. What am I missing here?
CodePudding user response:
I would suggest introducing a new Map remainderToItem
, looping through all relevant items and adding their reminder to the Map as key and item key as the value
then iterate the relevantItems
Map again to find the price is matching with some other reminder
Also check remainderToItem.get(entry.getValue()).equals(entry.getKey()))
(in case the value is 50 reminder is also 50), this prevents adding same item again to itemsThatCanBeBought
private static List<String> getTwoItemsWhichSumTo100(Map<String, Integer> items, int target) {
Map<String, Integer> relevantItems = getRelevantItems(items, target);
Map<Integer, String> remainderToItem = new HashMap<>();
List<String> itemsThatCanBeBought = new ArrayList<>();
for (Map.Entry<String, Integer> entry : relevantItems.entrySet()) {
int remainder = target - entry.getValue();
remainderToItem.put(remainder, entry.getKey());
}
for (Map.Entry<String, Integer> entry : relevantItems.entrySet()) {
if (remainderToItem.containsKey(entry.getValue()) && !remainderToItem.get(entry.getValue()).equals(entry.getKey())) {
itemsThatCanBeBought.add(entry.getKey());
itemsThatCanBeBought.add(remainderToItem.get(entry.getValue()));
return itemsThatCanBeBought;
}
}
return itemsThatCanBeBought;
}
private static Map<String, Integer> getRelevantItems(Map<String, Integer> items, int target) {
Map<String, Integer> relevantItems = new HashMap<>();
for (Map.Entry<String, Integer> entry : items.entrySet()) {
if (entry.getValue() < target) relevantItems.put(entry.getKey(), entry.getValue());
}
return relevantItems;
}
CodePudding user response:
the problem you're facing is that the int is the value , not the key.
so pairOfItems.containsKey(remainder)
should not compile.
luckily for you, Map also has containsValue()
method. as long as there is no requirement for minimum performance, that should solve your problem.
...and you don't need a 2nd map. you can just ask items.containsValue(reminder)