- 首先想到的还是hashmap
- 具体思路很简单,将所有值放入map的value部分,因为可能有重复,所以不能放在key部分。
- 这里使用Map.Entry的方式进行遍历,效率会高点。遍历的同时判断map是否有这个value和sum-value;如果有就更新temp,当然首先清空list,再放入新的元素。
- 遍历一次map即可
结果
运行时间12ms
内存消耗9412k
import java.util.ArrayList; import java.util.HashMap; import java.util.Map; import java.util.Set; import java.util.Collections; public class Solution { public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) { HashMap<Integer,Integer> map = new HashMap<>(); ArrayList<Integer> list = new ArrayList(); int temp = Integer.MAX_VALUE; for(int i=0; i<array.length; i++){ map.put(i,array[i]); } Set<Map.Entry<Integer, Integer>> entry = map.entrySet(); for(Map.Entry<Integer, Integer> en: entry){ if(map.containsValue((sum-en.getValue())) && (sum-en.getValue())*en.getValue()<temp){ list.clear(); temp = (sum-en.getValue())*en.getValue(); list.add(en.getValue()); list.add(sum-en.getValue()); } } Collections.sort(list); return list; } }