leetcode【哈希表—简单】1.两数之和

文章目录

• 前言
• 题目
• 题解
• NO1：暴力求解（O(N^2^)）
• NO2：map构建哈希表解决
• NO3：map+双指针(最优)
• 参考文章

前言

哈喽，我是长路，目前刚刚大三，方向是后端也偶尔捣鼓下前端，现在的主语言是Java。之前一大段时间都是在学习web开发的一些技术，就很久没有进行类似于数据结构、算法之类的学习与刷题，打算这段时间拾起来好好学一学、搞一搞。

这段时间也是机缘巧合看到草帽路飞的博客，加了自学群，正巧看到博主组织在群里组织了leetcode刷题打卡活动，我也就参与进来，为期一个月，打算坚持每天都花一些时间做一些题目，并通过博客的方式来进行记录。

目前跟着一个Github仓库刷题(leetcode)：代码随想录leetcode刷题，当前为哈希表专题。

---

题目

题目来源leetcode

leetcode地址：1. 两数之和，难度：简单。

题目描述(摘自leetcode)：

给定一个整数数组 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
只会存在一个有效答案

本地调试代码：

class Solution {

    public int[] twoSum(int[] nums, int target) {
        ...
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(new Solution().twoSum(new int[]{2,7,11,15},9)));
    }

}

---

题解

NO1：暴力求解（O(N^2^)）

思路：两层遍历循环来进行匹配两数之和。

代码：时间复杂度O(n^2^)

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[]{};
}

---

NO2：map构建哈希表解决

思路：利用HashMap来进行存储，key为遍历值，value为下标。每遍历一个元素值v时，直接计算target-v的值也就是待求的另一部分值，使用map来进行key索引看是否存在，一旦存在就表示匹配到了直接返回，不存在当前遍历值作为key，索引为value进行存储。

代码：O(n)

public int[] twoSum(int[] nums, int target) {
    int[] res = new int[2];
    if (nums == null || nums.length < 2) {
        return res;
    }
    Map<Integer, Integer> map = new HashMap<>(nums.length / 2 + 1);
    for (int i = 0; i < nums.length; i++) {
        //nums[i] + ? = target，这里直接使用map来进行匹配是否之前有某个数
        int temp = target-nums[i];
        //一旦匹配，直接赋值进行返回
        if(map.containsKey(temp)){
            res[0] = i;
            res[1] = map.get(temp);
        }
        map.put(nums[i],i);
    }
    return res;
}

---

NO3：map+双指针(最优)

思路：其实与NO2核心思想是一致的，再此基础上使用了两个指针分别指向最左边与最右边，在使用map存储时，一次遍历相当于前后两个位置同时进行，能够大幅度提升效率。

代码：O(n)

public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> map = new HashMap<>();
    int left = 0;
    int right = nums.length-1;
    for(;left<=right;left++,right--){
        if(map.containsKey(target-nums[left])){
            return new int[]{left,map.get(target-nums[left])};
        }
        map.put(nums[left],left);
        if(map.containsKey(target-nums[right]) && left!=right){  //避免中间相等的出现存储两次情况
            return new int[]{right,map.get(target-nums[right])};
        }
        map.put(nums[right],right);
    }
    return new int[2];
}

---

参考文章

[1]. leetcode题解

[2]. 代码随想录—两数之和

---

我是长路，感谢你的耐心阅读。如有问题请指出，我会积极采纳！ 欢迎关注我的公众号【长路Java】，分享Java学习文章及相关资料 Q群：851968786 我们可以一起探讨学习 注明：转载可，需要附带上文章链接

整理者：长路 时间：2021.10.18