leetcode1. 两数之和

题目描述

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

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

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

示例

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

题目分析

简单题目，在数组中找两个数加起来等于目标数，返回这两个数在数组中的下标。也就是你要保证顺序不能变，或者说能找到原来的顺序。下面提供了两种解法以及一个思路可以自己实现一下。

解法1

暴力解法，直接两次遍历数组，每次判断相加是否等于目标值，等于则直接返回，时间复杂度O(n^2)。

public int[] twoSum(int[] nums, int target) {
    //1.暴力解法，直接两次遍历找
    for (int i = 0 ; i < nums.length ; i ++) {
        for (int j = 0 ; j < nums.length ; j ++) {
            if (nums[i] + nums[j] == target) {
                return new int[]{i, j};
            }
        }
    }
    return null;
}

解法2

现在要提高效率，最容易想到的就是以空间换时间，这里用hashMap记录每个数值key以及数值的位置value，但是数组中可能存在相同的数，这时候我们该怎么处理呢？观察题目，找到两个数，那么当存在两个一样数值的数的时候，要么就是这两个数，要么只需要其中一个数另一个丢弃即可，此时我们就可以直接判断，两数之和是否等于目标值，等于直接返回，不等于丢弃后面遇到的数值，这样处理后时间复杂度为O(n)。

public int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> numMap = new HashMap<>();
    for (int i = 0 ; i < nums.length ; i ++) {
        if (numMap.containsKey(nums[i])) {
            //有个数出现两次
            if (nums[i] << 1 == target) {
                return new int[]{numMap.get(nums[i]), i};
            }
            continue;
        }
        numMap.put(nums[i], i);
    }
    for (int i = 0 ; i < nums.length ; i ++) {
        int sec = target - nums[i];
        if (sec != nums[i] && numMap.containsKey(sec)) {
            return new int[]{i, numMap.get(sec)};
        }
    }
    return null;
}

其他解法

思路：copy一个数组进行排序，遍历数组+二分查找，最后到原数组中找到位置。