题目描述

原题连接

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

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

个人解法

JavaScript

解法比较暴力

使用两层循环

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var len = nums.length;
    for (var i = 0; i < len - 1; i++) {
        var j = i + 1;
        var sum = undefined;
        while (target !== sum && j < len) {
            sum = nums[i] + nums[j];
            if (target == sum && j != i) {
                return [i, j];
            } else {
                j++;
            }
        }
    }
};

第一次刷题，遇到的问题：

1. while 循环内 未 加 条件 j < len。循环无法终止
2. 输入的 数组 为 [0,4,3,0] target = 0 时候 若 sum 初始值为 0 则 返回结果 为 undefined

Java

更优解法

看完之后 看了一下别人的题解

结合了下 哈希表的思路

Java

标签：哈希映射
这道题本身用暴力解法是比较容易解决的，但时间复杂度较高，为O(n_2)。而哈希查找的时间复杂度为_O(1)，所以可以利用哈希容器map降低时间复杂度。
遍历数组nums，i(下标为我们设的key值)为当前数组下标，遍历到每个数组元素时，判断map中是否存在target-nums[i]的key值。如果存在则找到了两个值，如果不存在则将当前的（nums[i]，i）存入map中，继续遍历直到找到为止。

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer,Integer>harshtable=new HashMap<>();
        for(int i=0;i<nums.length;i++){
            if(harshtable.containsKey(target-nums[i])){
                return new int[] {harshtable.get(target-nums[i]),i};
            }
            harshtable.put(nums[i],i);
        }
        return new int[0];
    }
}

画解：

1.

2.

3.

4.

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var temp = [];
    for(var i=0;i<nums.length;i++){
        var dif = target - nums[i];
        if(temp[dif] != undefined){
            return [temp[dif],i];
        }
        temp[nums[i]] = i;
    }
};