力扣leetcode题目分析——两数之和

男娘i 2024-04-18 12:43 69阅读 0赞

## 说明 ##

同学跟我说要多在力扣上面刷题，这样才能越来越厉害，据说有些大牛之所以为大牛，就是因为在上面刷了一两年。哈哈哈，开个玩笑。不过如果坚持做下去，应该收获很大吧。像我这种学渣，只能从最简单的开始，接受大家的鄙视。题目用的是力扣的题目，题目中的示例用的也是力扣中的题，力扣网站为https://leetcode-cn.com/

## 运行环境 ##

java语言

## 鸡汤 ##

下面最近很喜欢一句话，决定每天晚上睡觉前念一遍，写个毒鸡汤，大家共勉吧。  
**我所拥有的，都是我努力得来的，我所失去的，都是我未曾真正拥有的**  
下面进入正题

## 题目 ##

1.两数之和  
给定一个整数数组nums和一个目标值target，请你在该数组中找出和为目标值的那**两个**整数，并返回他们的数组下标。

示例

> 给定nums = \[2, 7, 11, 15\], target = 9  
> 因为nums\[0\] + nums\[1\] = 2 + 7 = 9  
> 所以返回\[0, 1\]

**解答**  
Java语言

class Solution {
        public int[] twoSum(int[] nums, int target) {
            int[] result=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){
                        result[0]=i;
                        result[1]=j;
                    }
                }
            }
            return result;
        }

结果好像比较差：  
![在这里插入图片描述][20190906181010760.png]  
后来我想了一下，好像不需要最后都遍历完了再返回，一旦找到了了符合条件的就可以返回了，所以我在if语句中加入了return。

class Solution {
        public int[] twoSum(int[] nums, int target) {
            int[] result=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){
                        result[0]=i;
                        result[1]=j;
                        return result;
                        //在这里加入return，当找到符合条件的就返回，不用继续遍历完后面的
                    }
                }
            }
            return result;
        }
    }

试一下结果，好像有了一点点改善：  
![在这里插入图片描述][20190906182719720.png]  
我们这道题到现在其实用的更多是遍历，我看到有一个网友null-ecp的解法特别好，在这里分享一下，他是通过Map集合，把两个数中的一个数作为键，另外一个数作为值来存的，这样就可以很快找到想要的两个数。而且他采用的是HashMap，性能会更高一点。在这里分享一下，我还是用result表示结果，里面的注释我没有用null-ecp的，我自己写了个注释，帮助更好理解。  
先讲一下这道题中涉及到的HashMap的知识吧，复习一下。

## HashMap ##

HashMap为散列表结构，Map集合都是键值对的存储结构，通过键（key）能很快找到对应的值（value），其中键是无序不重复的，值是无序可重复的，即键是唯一的。我们一般采用它的无参数构造方法来创建一个对象，泛型则是根据具体情况来选择的，这里因为集合中键值对存储的都是int型的，所以这里的泛型采用Integer。  
put(key k,value v)方法是HashMap用来存键值对的，remove(key k)方法用来删除键值对，get(key k)方法则是通过键来取值。另外这道题还用到另一个方法containsKey(key k)，这个方法是用来判断集合中是否存在某个键（key）的，当然HashMap中也有一个方法containsValue(value v)是用来判断集合中是否存在某一个值（value）的。  
下面看代码：

//记得使用HashMap要导包
    class Solution {
        public int[] twoSum(int[] nums, int target) {
           //用int数组来存储结果
            int[] result=new int[2];
            //接下来创建HashMap对象
            HashMap<Integer,Integer> hashMap=new HashMap<Integer,Integer>();
            //遍历——这里遍历实现存值以及判断是否有符合条件的两个数出现
            for(int i=0;i<nums.length;i++){
            //判断是否有满足条件的两个数，有则存进结果里（具体解释看下一个注释）
                if(hashMap.containsKey(nums[i])){
                    result[1]=i;
                    result[0]=hashMap.get(nums[i]);
                    return result;
                }
                /*集合中的键存储的是target-nums[i]，集合中存了nums长度个键值对，
                键是用目标值减去所给nums数组中每一个元素，有点类似于取反码，
                值存的是nums数组此时遍历到的元素的下标，所以如果数组中存在
                两个相加等于target的数，则在遍历到其中一个数的时候，它的存储在Map
                中的键一定会等于另一个数的值。所以如果存在键值对中的键与nums中
                某一个元素相等，则键就是其中一个数，下标为遍历的i值，另一个数的
                下标就是这个键对应的值*/
                hashMap.put(target-nums[i],i);
                //存值
            }
            return result;
        }
    }

据说执行结果是这样的：  
执行用时 :3 ms, 在所有 Java 提交中击败了99.06%的用户  
这里就不给结果图了。

[20190906181010760.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/e2d9d7ff47064d978283f37109776132.png
[20190906182719720.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/18/12a0d8083aae4ca0bb6f7b03cdb2c7c3.png