金三银四就要到了,阿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就做到这里,咱们下期见!