[Java·算法·简单]LeetCode1. 两数之和等于目标值

偏执的太偏执、 2023-09-24 20:20 88阅读 0赞

#### 每天一题，防止痴呆 ####

*  题目
 *  示例
 *  分析思路1
 *  题解1
 *  分析思路2
 *  题解2

## 题目 ##

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

你可以假设每种输入只会对应一个答案。  
数组中同一个元素在答案里不能重复出现。  
你可以按任意顺序返回答案。

## 示例 ##

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

输入：nums = [3,2,4], target = 6
    输出：[1,2]

输入：nums = [3,3], target = 6
    输出：[0,1]

## 分析思路1 ##

使用双重循环，第一层遍历数组每个元素，第二层遍历这个数组之后的每个元素，两层元素相加等于`target`即可

## 题解1 ##

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

执行结果  
![在这里插入图片描述][08b06d391f084e39999fb3a53fe77a01.png]

## 分析思路2 ##

可以使用哈希表来解决，我们可以创建一个 map，用来存储数组中每个元素的值以及其下标。然后，我们遍历数组，对于每个元素 nums\[i\]，我们在哈希表中查找是否存在一个元素等于 target - nums\[i\]，若存在，则找到了这两个元素，其下标分别为 i 和哈希表中对应元素的下标。

## 题解2 ##

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            Map<Integer,Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {
        
                int otherOne = target - nums[i];
                if(map.containsKey(otherOne)){
        
                    return new int[]{
        i, map.get(otherOne)};
                }
                map.put(nums[i],i);
            }
            return new int[0];
        }
    }

执行结果  
![在这里插入图片描述][d547bb29efdb459683b8ff2305b37309.png]

[08b06d391f084e39999fb3a53fe77a01.png]: https://img-blog.csdnimg.cn/08b06d391f084e39999fb3a53fe77a01.png
[d547bb29efdb459683b8ff2305b37309.png]: https://img-blog.csdnimg.cn/d547bb29efdb459683b8ff2305b37309.png