卷进大厂系列之LeetCode刷题笔记：两数之和（简单）

2年前 (2022) 程序员胖胖胖虎阿

139 0 0

学算法，刷力扣，加油卷，进大厂！

题目描述

力扣题目链接

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 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]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

涉及知识点

本题解题思路有很多，本文考虑两个解题思路：暴力解法和利用哈希表；

对于数组我们要知道以下内容：

数组是存储在连续内存空间的相同类型数据的集合
数组下标都是从0开始
数组在内存空间的地址都是连续的

对于哈希表我们要知道以下内容：

数组是一个简单的哈希表，其中哈希表中的关键码就是数组的索引下标
哈希表可以根据关键码直接访问数据（可以在 O(1) 的时间内判断一个元素是否在集合中）

那么根据题目，我们可以提炼的关键点：

返回数组下标
数组中同一个元素在答案里不能重复出现
数组长度大于等于2

这是一道简单的题目，最先想到的就是暴力方法，直接使用双重for循环就可以解决问题；但是这样会非常耗时，因此这时的数组并不是一个很好用的数据结构，我们可以考虑到哈希表的map，它拥有<key,value>的数据结构，其中key用来保存值，value用来保存数组所在的下标，即我们前面说到的我们可以根据其关键码直接访问其数据，这样就可以快速寻找数组中是否存在目标元素及其对应下标。

题目解答

Java题解一

思路分析

直接使用双重for循环遍历两个数组，然后进行求和，与题目所给target进行比较，但是我们需要注意的是，题目要求数组中同一个元素在答案里不能重复出现，那只使用数组自然不容易避免这种情况，所以我们在这里使用HashSet来存储满足条件的值（HashSet介绍）。

创建HashSet用来存放满足条件的值
使用双重for循环遍历两个数组，进行求和，满足条件的值，放入HashSet中
创建一个数组，将HashSet中的元素放入数组

代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {

        Set<Integer> set = new HashSet<>(); //创建一个哈希表，用来存数满足条件的值
        //暴力解法：双重for循环
        for(int i = 0; i < nums.length - 1; i++){ //求和的第一个元素
            for(int j = i + 1; j < nums.length; j++){ //求和的第二个元素；遍历第一个元素后的元素
                if((nums[i]+nums[j]) == target){ //如果两个元素和等于target，将其添加到哈希表中
                    set.add(i);
                    set.add(j);
                }
            }
    }
    int[] result = new int[set.size()]; //创建一个输出结果的数组
    int index = 0;

    for(int i : set){ //遍历哈希表
         result[index] = i; //将哈希表中的元素放入数组
            index++;//数组后移一位
    }

    return result; //输出结果
    }
}

卷进大厂系列之LeetCode刷题笔记：两数之和（简单）

Java题解二

思路分析
使用哈希表是对上一个方法的改进，因为我们上一个方法两次for循环是非常耗时的，所以这是一个很关键的改进点，我们利用哈希表中的map来解决这个问题。这时候我们只需要执行一遍for循环，得到target与数组中的差值，然后再直接查看map是否有刚刚的差值，如果满足条件，就把对应的下标放入结果数组。

创建结果数组，哈希表HashMap
遍历数组，求出target与数组的差值temp
利用map的containsKey方法，判断是否满足条件，满足的话，放入结果数组

代码实现

class Solution {
    public int[] twoSum(int[] nums, int target) {
        //使用map来解决，<key,value>;
        int[] result = new int[2]; //定义结果数组
        HashMap<Integer,Integer> map = new HashMap<>(); //定义HashMap

        for(int i = 0; i < nums.length; i++){ //循环数组
            int temp = target - nums[i];    //用target减去数组中的值，得到临时temp
            if(map.containsKey(temp)){  //看下map里面是否有temp（有的话就满足题目条件）
                result[1] = i; //将i值先放到结果数组中
                result[0] = map.get(temp); //将map中的temp赋给结果数组
            }
            map.put(nums[i],i); //使用put方法，将num[i]放到结果数组中（Map 集合中对应键名的键值对象）
        }
        return result;//输入结果
    }
}