LeetCode in JavaScript#1 Two Sum

Leetcode Two Sum

Solution1

简单粗暴地遍历所有情况

var twoSum = function(nums, target) {
    var i,len = nums.length;
    for (i=0;i<len-1;i++) {
        for (j=i+1;j<len;j++) {
            if (nums[i] + nums[j] === target) {
                return [i,j];
            }
        }
    }
};

时间复杂度 O(n^2)
空间复杂度 O(1)

Solution2

将js对象当做hashtable来使用，key是数组元素的值，value是数组元素的索引，只遍历一次数组，每次先查找哈希表中是否有匹配的元素，如果没有就将现有元素添加进哈希表中

var twoSum = function(nums, target) {
    var i,j,len = nums.length;
    var hash = {};
    for (i=0;i<len;i++) {
        j = target-nums[i];
        if (hash[j] !== undefined)
            return [i,hash[j]];
        else 
            hash[nums[i]] = i;
    }
};

时间复杂度 O(n)
空间复杂度 O(n)