ACM之两数之和问题
题⽬如下：
⼤概的意思是：给我们⼀个Int型的数组和⼀个⽬标值，出数组中两个值之和为⽬标值的元素位置；要求是每个输⼊对应⼀个答案（即到符合条件的元素直接返回结果就⾏，不⽤继续往后，难度降低）并且相同的元素值不能⽤两次。 1.刚开始的思路：
伟⼤⽽⼜万能的蛮⼒法，⽤两个for循环，很容易求解，时间复杂度为O(N^2)，代码如下：
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
for(int i = 0;i < nums.length;i++){
for(int j = i+1;j < nums.length;j++){
if((nums[i]+nums[j]) == target){
res[0] = i;
res[1] = j;
return res;
}
灸除百病}
}
中国人的焦虑从哪里来
return res;
}
危险固体废物}
2.优化解法
蛮⼒法虽然是我这种菜鸟的最爱，可惜不是⾯试官要的答案，还是不能将就的。想办法把时间复杂度将为O(N)就很爽了啊，也就是把上⾯蛮⼒法中的⼀个for循环给去掉，怎么弄呢？蛮⼒法的思路是不断地进⾏a+b去匹配⽬标值c，既然⽬标值知道，那我们当然可以选择c-b去匹配a。⽤⼀个for循环将c-b的值存在⼀个数据结构中，然后查这个数据结构中是否含有a就⾏。那么问题来了，这个数据结构选什么呢：数组？栈？队列还是HashMap？⼀看前⾯三种选择查的时间复杂度还是
中国核应急救援队O(N)，⽽HashMap查的时间复杂度为O(1)，那肯定选HashMap，问题都搞定了，代码实现出来就OK：
public class TwoSumBter {
public static int[] twosum(int[] num,int target){
int[] res = new int[2];
int len = num.length;
//判断输⼊数组的⼤⼩
if(num == null || num.length<2){
res[0] = 0;
res[1] = 0;
return res;
}
//建⽴HashMap
HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();
for(int i=0;i<len;i++){
/
/判断HashMap中是否含有⽬标数组中的数
ainsKey(num[i])){
res[0] = hm.get(num[i]);
res[1] = i;
return res;
}else{
hm.put((target-num[i]), i);
}
}
return new int[]{0,0};
}
}
个旧市和平小学>电气石粉
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议