LeetCode题：1：两数之和

水深无声 2024-02-20 09:55 84阅读 0赞

> ## （1）、题目要求： ##
> 
> ![981be1c719a14ae091a46ab5ab6bf88b.png][]

> ## （2）、解题思路： ##
> 
> ![919a69db43ee4118b8f79596988b8fb6.png][]
> 
> 由上图可知，target = 20，这题有多种解法
> 
> **1、暴力枚举的方法：**
> 
> 但是这样时间复杂度就很高了，要定义两个下标，列举出所有两个不同元素相加的值，同时记录下标，看是否等于target，**把符合要求的那两下标放在一个新的数组中，再返回新的数组**，时间复杂度为O(N^2)；
> 
> **2、使用HashMap的方法：**
> 
> 我们**遍历一遍数组**，每得到nums\[i\]这个元素，都判断map里面有没有nums\[i\]这个元素，**如果没有，就要把nums\[i\]的值和i下标放进map中，有的话就把i和map里值为num\[i\]的下标放进一个新的数组，返回这个新的数组**，注意：**map里的key为nums的元素，val为nums元素的下标**，时间复杂度：O(N)。

> ## （3）、代码示例： ##
> 
> **1、暴力枚举方法：**
> 
>     class Solution {
>         public int[] twoSum(int[] nums, int target) {
>             HashMap<Integer, Integer> map = new HashMap<>();
>             for(int i = 0; i < nums.length; i++) {
>                 map.put(i, nums[i]);
>             }
>             //再次遍历一遍数组，i和后面的元素依次计算，穷举完，判断两下标元素相加是否==target
>             int flg1 = 0;
>             int flg2 = 0;
>             for(int i = 0; i < nums.length; i++) {
>                 for(int j = i + 1; j < nums.length; j++) {
>                     if(map.get(i) + map.get(j) == target) {
>                         flg1 = i;
>                         flg2 = j;
>                         break;
>                     }
>                 }
>                 if(flg1 != 0) {
>                     break;
>                 }
>             }
>             int[] num = {flg1, flg2};
>             return num;
>         }
>     }
> 
> **2、使用HashMap方法：**
> 
>     class Solution {
>         public int[] twoSum(int[] nums, int target) {
>             //把nums的元素下标和元素值都房间一个map中，然后遍历一遍nums，每遍历一次，都找map里面有没有[i]这个值，有就把把i下标值和map里这个值的下标放进一个新的数组中，再返回这新的数组
>             HashMap<Integer, Integer> map = new HashMap<>();
>             int[] array = new int[2];
>             for(int i = 0; i < nums.length; i++) {
>                 int x = target - nums[i];
>                 if(!map.containsKey(x)) {
>                     map.put(nums[i], i);
>                 } else {
>                     array[0] = i;
>                     array[1] = map.get(x);
>                     break;
>                 }
>             }
>             return array;
>         }
>     }

[981be1c719a14ae091a46ab5ab6bf88b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/959c233c18464de18dd456175751237a.png
[919a69db43ee4118b8f79596988b8fb6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/20/a5bcfb7c2c49404196f7b3d4853cf6a9.png