LeetCode每日一题: 1. 两数之和

清疚 2022-11-04 05:56 194阅读 0赞

> 微信公众号：**Java随笔录**  
> 关注可了解更多Java相关的技术分享。问题或建议，欢迎公众号留言！  
> **如果你觉得JiangNanMax对你有帮助，欢迎赞赏！**

### 文章目录 ###

*   *   *  题目
         *  题目大意
         *  解题思路
         *  代码
         *  公众号
         *  赞赏

### 题目 ###

*  [https://leetcode-cn.com/problems/two-sum/][https_leetcode-cn.com_problems_two-sum]

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

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

你可以按任意顺序返回答案。

**示例**：

示例 1：
    
    输入：nums = [2,7,11,15], target = 9
    输出：[0,1]
    解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
    
    示例 2：
    
    输入：nums = [3,2,4], target = 6
    输出：[1,2]
    
    示例 3：
    
    输入：nums = [3,3], target = 6
    输出：[0,1]

### 题目大意 ###

在数组中找到两个数之和等于给定值的数字，结果返回这两个数字在数组中的下标。

### 解题思路 ###

这道题最优的做法时间复杂度是O(n)。

顺序扫描数组，对每一个元素，在map中找能组合给定值的另一半数字，如果找到了，直接返回这两个数字的下标即可。如果找不到，就把这个数字存入map中，等待扫到“另一半”数字的时候，再取出来返回结果。

### 代码 ###

class Solution { 
        /** * 遍历数组，用map存储元素值与其index的关系 * 为节约空间和时间，遍历的同时进行查找，满足条件即可结束循环 * @param nums * @param target * @return */
        public int[] twoSum(int[] nums, int target) { 
            Map<Integer, Integer> value2index = new HashMap<>();
            for (int i = 0; i < nums.length; i++) { 
                if (value2index.containsKey(target - nums[i])) { 
                    return new int[] { value2index.get(target - nums[i]), i};
                } else { 
                    value2index.put(nums[i], i);
                }
            }
            return null;
        }
    }

### 公众号 ###

*  关注公众号，即时接收关于Java的技术分享！

![20210207183855124.JPG][]

### 赞赏 ###

*  如果你觉得JiangNanMax对你有帮助，欢迎赞赏，有你的支持，JiangNanMax一定会更加努力！

![20210207184039797.JPG][]

[https_leetcode-cn.com_problems_two-sum]: https://leetcode-cn.com/problems/two-sum/
[20210207183855124.JPG]: /images/20221023/4d2efc1507564efeb870e4a789caec1f.png
[20210207184039797.JPG]: /images/20221023/cf40ee760e97405fb2007d4da6f84278.png