LeetCode-1.两数之和

Leefs 2020-02-15 PM 1749℃ 0条

# LeetCode-1.两数之和

# 题目

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的 两个 整数。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

> 给定 nums = [2, 7, 11, 15], target = 9
> 因为 nums[0] + nums[1] = 2 + 7 = 9
> 所以返回 [0, 1]

解法一：

通过暴力搜索进行解决。

```java
public static int[] twoSum(int[] arr,int target){
    int[] sumIndex = new int[2];
    for(int i=0;i<arr.length;i++){
        for(int j=i+1;j<arr.length;j++){
            if(arr[i]+arr[j]==target){
                sumIndex[0]=i;
                sumIndex[1]=j;
            }
        }
    }
    return sumIndex;
}
```

该段代码比较容易理解，就不进行详细介绍了。

解法二：

使用哈希表解答

```java
public static int[] twoSum2(int[] nums,int target){
    Map<Integer,Integer> map = new HashMap<>();
    for(int i=nums.length-1;i>=0;i--){
        int firstNum = target - nums[i];
        if(map.containsKey(firstNum)){
            return new int[]{i,map.get(firstNum)};
        }else{
            map.put(nums[i],i);
        }
    }
    throw new IllegalArgumentException();
}
```

1. 1.创建一个map集合对象，key用来存储数组中的值，value用来存储数组中值对应的位置下标。

2. 2.对数组从后向前进行倒序遍历
3. 3.用所要得到的总和减去数组中遍历到的数
4. 4.获得相减后的值进行判断在map集合中是否存在，如果存在就找到，如果不存在将数组中遍历到的值和对应的数组角标存入到map集合中，进行后序查找比较。
5. 5.如果找到就返回遍历到的角标的位置和取出集合中对应的值

标签: none

非特殊说明，本博所有文章均为博主原创。

如若转载，请注明出处：https://lilinchao.com/archives/609.html

上一篇数据结构和算法学习--堆排序

下一篇 LeetCode-2 两数相加

LeetCode-1.两数之和

评论已关闭

栏目分类

标签云

友情链接申请

LeetCode-1.两数之和

评论已关闭

 栏目分类

标签云

友情链接申请

栏目分类

标签云

友情链接申请