跟着数学系阿du开启算法刷题之旅 不来了解下?

金三银四就要到了,阿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(跟着数学系阿du开启算法刷题之旅 不来了解下?),可不可以降低为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就做到这里,咱们下期见!

上一篇:SpringBoot+SparkSQL操作JSON字符串


下一篇:linux 磁盘空间满了