leetcode算法题1——两数之和（难度：简单）

短命女 2022-12-22 02:27 144阅读 0赞

## 一。题目 ##

**两数之和：**

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

**示例:**

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

## 二。解答 ##

这道题还是比较简单，常规思路可以用两个for循环暴力破解：

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            
            for(int i=0;i<nums.length;i++){ 
                for(int j=0;j<nums.length;j++){ 
                    if(i!=j && nums[i]+nums[j]==target){ 
                        return new int[]{ i,j};
                    }
                }
            }
            return null;
        }
    }

但是两个for循环套用导致性能很低，程序运行时间超出的时间限制：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70_pic_center]  
参看评论区大佬的code之后，发现可以用一个简单的hashmap实现，且性能高效，代码如下：

class Solution { 
        public int[] twoSum(int[] nums, int target) { 
            HashMap<Integer,Integer> map = new HashMap<>();
            for(int i = 0; i < nums.length; i++){ 
                //查看map中是否含有该key
                if(map.containsKey(nums[i])){ 
                    return new int[]{ map.get(nums[i]), i};
                }
                map.put(target - nums[i], i);
            }
            return null;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NDAwOTQ0Nw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/7b59e963c18840babac9e0e1d2103376.png