Careercup April 19
今天做了 一道题，感触很大，给一组数 arraylist{2,9,11,3,5,6,34,22}
target=14
找到其中两数之和是target 的数的index
想了一个办法先built 数组
Use loop do go over the entire list
O(n^2)
发现网上大牛的解法佩服的不行O(n)
int add(ArrayList al){
int target=11;
boolean found=false;
HashMap map = new HashMap();
for (int i = 0; i < al.size(); ++i) {
Integer temp = map.get(target - Integer.parseInt(al.get(i).toString()));
if (temp == null) {
map.put(Integer.parseInt(al.get(i).toString()), i);
} else {
found = true;
System.out.println(String.format("Given sum %d, found %d at index %d and %d at index %d.", target,Integer.parseInt(al.get(i).toString()), i, target - Integer.parseInt(al.get(i).toString()), temp));
}
}
用HashMap,连table 都不用建立。
Go over 一遍就可以了，用(target-al(i))，做HashMap
大赞！！！
target=14
找到其中两数之和是target 的数的index
想了一个办法先built 数组
Use loop do go over the entire list
O(n^2)
发现网上大牛的解法佩服的不行O(n)
int add(ArrayList al){
int target=11;
boolean found=false;
HashMap
for (int i = 0; i < al.size(); ++i) {
Integer temp = map.get(target - Integer.parseInt(al.get(i).toString()));
if (temp == null) {
map.put(Integer.parseInt(al.get(i).toString()), i);
} else {
found = true;
System.out.println(String.format("Given sum %d, found %d at index %d and %d at index %d.", target,Integer.parseInt(al.get(i).toString()), i, target - Integer.parseInt(al.get(i).toString()), temp));
}
}
用HashMap,连table 都不用建立。
Go over 一遍就可以了，用(target-al(i))，做HashMap
大赞！！！
评论