leetcode Algorithms task 1

发表于   |   分类于   |  

Difficulty: Easy

问题描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example:

1
2
3
Given nums = [2, 7, 11, 15], target = 9,    
Because nums[0] + nums[1] = 2 + 7 = 9,    
return [0, 1].

方法一：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var temp,flag;
    for(var i = 0; i < nums.length; i++){
        temp = target - nums[i];
        flag = nums.indexOf(temp);
        if(flag != -1 && flag != i){
            return [i, flag];
        }
    }
};

方法一结果分析如图：

结果分析图1.1

方法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var result = [],
    map = {};
    for(var i = 0; i < nums.length; i++){
        if(typeof(map[target - nums[i]]) !== 'undefined'){
            result.push(map[target - nums[i]]);
            result.push(i);
        }
        map[nums[i]] = i;
    }
    return result;
};

###方法二结果分析如图：
结果分析图1.2

总结

从性能分析中来看显然方法二的性能远远优于方法一，利用建立字典集，在字典集中查找的时间复杂度要远低于利用indexOf()函数。