leetcode算法题1——两数之和(难度:简单) 短命女 2022-12-22 02:27 98阅读 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
还没有评论,来说两句吧...