Leetcode 1.两数之和

Leetcode 算法

Leetcode

发布日期: 2023-07-07

更新日期: 2023-10-16

文章字数: 1k

阅读时长: 3 分

阅读次数:

Leetcode 1.两数之和

1. 题目说明

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

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

2. 解答分析

本题有好多种解法，这里选择两种常见的解法，一种是直接上循环，不断遍历数组；另外一种是利用哈希表，返回对应表的下标（利用key 和value）

方法1：利用遍历模拟

本题要求的是返回两个数字和为target的数组元素的下标，这里可以直接交换遍历，比如最简单的for循环，我们会把两个指针所指向的值之和，依次比较，最后返回数组元素的下标（构建新的数组）

class Solution{
    public int[] twoSum(int []nums,int target){
        int j=1;
        int i=0;
        int maxLen=nums.length-1;
        while(nums[i]+nums[j]!=target){
            if(j==maxLen)}{
            	i++;
            	j=i;
        }
        j++:
        }
    return new int[]{i,j};
    }
}

时间复杂度：O(n²),一个是i，另外一个是j的循环遍历，至少需要**n(n-1)**的步骤；空间复杂度为O(1)

方法2：Hash表

Hash表是一种数据结构关系，利用键(key)和值(value)的一一对应的关系，生成map。map目的用来存放我们访问过的元素，因为遍历数组的时候，需要记录我们之前遍历过哪些元素和对应的下标，这样才能找到与当前元素相匹配的（也就是相加等于target）

在遍历数组的时候，只需要向map去查询是否有和目前遍历元素匹配的数值，如果有，就找到的匹配对，如果没有，就把目前遍历的元素放进map中，因为map存放的就是我们访问过的元素

本题的map我们这样定义：key为数组中的num[i]值，对应的value为：下标元素i；

class Solution{
    public int[] twoSum(int[] nums,int target){
        int[]res=new int[2];//首先生成最后需要返回的数组，保存的是数组的元素下标
        if(nums==null || nums.length==0){
            return res;//考虑特例
        }
        Map<Integer,Integer>map=new HashMap<>();//建立HashMap
        for(int i=0;i<nums.length;i++){
            int temp=target-nums[i];//从第i个元素开始，看看当前的元素数组中是否存在可以满足条件的值
            if(map.containsKey(temp)){
                res[1]=i;
                res[0]=map.get(temp);//这里的get返回的是满足条件的temp数组元素的下标，注意我们定义Value是数组元素的下标，对应的Key是数组元素的值
                break;//跳出循环
            }
            map.put(nums[i],i);//如果没有找到匹配的对，对于大的循环而言，只需要在HashMap中添加对应的nums值和下标即可，为后续的元素查找匹配提供map数据资源。
        }
        return res;//返回需要的元素数组下标的新数组
    }
}