LeetCode_数组_简单_1.两数之和

目录

• 1.题目
• 2.思路
• 3.代码实现（Java）

1.题目

给定一个整数数组 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

只会存在一个有效答案

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/two-sum

2.思路

（1）暴力穷举法

暴力穷举法应该是最容易想到的方法，其思想是使用两层for循环，遍历数组中的每一个数x，查找数组中是否存在target-x，若存在，将结果保存到数组res中，并退出循环。

（2）哈希表法

先创建一个哈希表，对于数组真的每一个x，首先查询哈希表中是否存在target-x，如果不存在，则将x插入到哈希表中并继续访问下一个x，否则将答案保存到数组res中。不过该算法的一个缺点是需要用到一个hash表，这样一来增加了空间复杂度。

3.代码实现（Java）

//（1）暴力穷举法
public int[] twoSum(int[] nums, int target) {
    int[] res=new int[2];
    boolean flag=false;
    for(int i=0;i<nums.length;i++){
        for(int j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                res[0]=i;
                res[1]=j;                
                flag=true;
            }
        }
        //由于每种输入只会对应一个答案，所以当找到一种答案时，可以终止查找
        if(flag){
            break;
        }
    }
    return res;
}
           

//（2）哈希表法
public int[] twoSum(int[] nums, int target) {
    Map<Integer,Integer> ht = new HashMap<Integer, Integer>();
    for (int i=0;i<nums.length;i++) {
    	//containsKey():检查hashMap中是否存在指定的key对应的映射关系。
        if (ht.containsKey(target-nums[i])){
        	//get():获取指定key对应对value
            return new int[]{ht.get(target-nums[i]), i};
        }
        //当前未找到target-nums[i]，将nums[i]以及其数组下标保存到哈希表ht中，以便于下次寻找
        ht.put(nums[i], i);
    }
    return new int[0];
}