力扣刷题之求两数之和

力扣刷题之求两数之和

这道题是力扣的第一题，是刷题梦开始的地方。绝对不能小看，因为我很菜。

题目如下：

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。

在这里插入图片描述

题目的要求是给定一个数组，给定一个目标值，然后让你在数组中找到两个值的和等于目标值，然后返回它们的下标。

在这里插入图片描述

一般我们不会这么快找到目标数据。通常会存在一个遍历的过程。一次移动索引和后面的值相加。类似于这样。知道寻找到目标值。

在这里插入图片描述

这样的代码是这样实现的。

for (int i = 0; i < nums.length; i++) {
             for (int i1=i+1; i1 < nums.length; i1++) {
                 if(nums[i]+nums[i1]==target)
                 {
                    arr[0]= i;
                    arr[1]=i1;
                 }

             }
         }

按照这样的逻辑的话，我们还是用到了双重for循环，在查找目标值的时候，我们准会遍历到曾经遍历过的元素，这就是重复。

比如2+7 2+11 2+15 ···· 然后我们在使用7和后面的数相加的时候还是会去遍历11,15。 这样随着搜索次数遍历以及数据量的2增多，难免也是一个浪费时间效率的问题。

于是我们尝试这样去解决问题，能不能再遍历到这个元素之后，我们就把他记下来，然后下次用的时候不是直接用，这样多好。而且可以对应到值和下标。 现在这里是初始化，箭头就是遍历索引移动。

在这里插入图片描述

开始我们从4开始，4离目标值相差16,hashmap中一定是没有的，所以我们把4和它的索引放进去。

在这里插入图片描述

然后继续，到这里的时候我们走到7去查找13,发现map里面正好又这个key，于是我们正好将这个key对应的vaue返回，value就是索引。当然你反着来也是没有问题的。

在这里插入图片描述

想想，如果还是采用暴力穷举的话，那么是不是到了7我们还是for循环 那么就是 4+6 4+7 … 4+13 …

6+13 6+8 … 13+8 13+7 这样去找，我们进行了重复的遍历值，从这个小计算量就可以发现我们一共用了5次13,而我们如果用hashmap，我们就只经过它一次，将它记录，然后后面就可以直接找到它。是不是很方便。 实现代码

  HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int result = target-nums[i];
            if(map.containsKey(result))
            {
                map.get(result);
                arr[1]=i;
                arr[0]=map.get(result);
            }else {
                map.put(nums[i],i);
            }
        }

这个效率是非常高的。

在这里插入图片描述

简单是一方面，简单的题能不能去理解到位就是另一回事了。 简单的题都没有难一点的题通过率高。

在这里插入图片描述

有时候的理解知识暂时的理解，如果算法基础不扎实的话，会马上忘掉，然后再次陷入到疑惑当中。算法的基础是数据结构加基本语法知识。