金三银四就要到了,阿du提前带大家一起练练手,开启算法之旅!
力扣(LeetCode )首题(两数之和):给定一个整数数组 nums 和一个整数目标值 target,请在该数组中找出和为目标值 target的那两个整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
看到这道题,阿du直呼简单简单,上手就来,暴力破解,双层for循环解决如下:
public int[] twoSum(int[] nums, int target) {
for(int i=0;i<nums.length-1;i++){
//从该元素之后依次和这个元素求和判断看是否满足要求
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
return new int[]{i,j};
}
}
}
return new int[0];
}
但运行之后阿du发现费时较长,那么有没有更优的解法呢,阿du沉下心仔细分析了下,目前程序时间复杂度为O(),可不可以降低为O(n)呢,仔细看看程序是哪里费时了,当然不用多说一定是双层for循环惹得锅,那怎么能减少一层循环呢,主要是寻找一种方案来代替target-nums[i]的功能,阿du脑门一亮有了,我可以借助于java中的数据结构哈希表来实现呀,通过哈希表的键是否包含target-nums[i]来进行判断,这样就可以减少一层for循环,将时间复杂度降为O(n),代码实现如下:
public int[] twoSum(int[] nums, int target) {
//结果数组
int[] result = new int[2];
//利用哈希表来降低时间复杂度
Map<Integer,Integer> map = new HashMap();
for(int i=0;i<nums.length;i++){
//判断map中键是否包含即可判断是否有另一个值和该值之和等于目标值
if(map.containsKey(target-nums[i])){
result[0] = map.get(target-nums[i]);
result[1] = i;
break;
}
//将数组中值放在key的位置,对应下标放在value位置
map.put(nums[i],i);
}
return result;
}
伙伴们你们想到了嘛?今日一题 阿du就做到这里,咱们下期见!