LeetCode 算法题【Easy】：1. Two Sum

发表于 更新于 分类于 阅读次数： Disqus：

Question

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:

1
2
3
4
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:

1
2
3
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:

1
2
Input: nums = [3,3], target = 6
Output: [0,1]

My Answer

  • 初始答案
1
2
3
4
5
6
7
8
9
10
11
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i ++) {
        if (nums[i] < target) {
            const rest = nums.slice(i + 1)
            const index = rest.indexOf(target - nums[i])
            if (index !== -1) {
                return [i, index + i + 1]
            } 
        }
    }
};

  • 报错：

    • nums: [0, 2, 3, 0]
    • target: 0
    • 没有考虑 target 和 nums[i] 一样大的情况

  • 修改答案

1
2
3
4
5
6
7
8
9
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i ++) {
          const rest = nums.slice(i + 1)
          const index = rest.indexOf(target - nums[i])
          if (index !== -1) {
              return [i, index + i + 1]
          } 
    }
};

  • 报错

    • nums: [-1,-2,-3,-4,-5]
    • target: -8
    • 没有考虑负数的情况

  • 修改答案

1
2
3
4
5
6
7
8
9
var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i ++) {
        const rest = nums.slice(i + 1)
        const index = rest.indexOf(target - nums[i])
        if (index !== -1) {
            return [i, index + i + 1]
        } 
    }
};

My Answer’s Performance

1

Better Answer Reference

1
2
3
4
5
6
7
8
9
10
11
12
13
14
var twoSum = function(nums, target) {
		var ans = [];
    var exist = {};
    
    for (var i = 0; i < nums.length; i++){
        if (typeof(exist[target-nums[i]]) !== 'undefined'){
            ans.push(exist[target-nums[i]]);
            ans.push(i);
        }
        exist[nums[i]] = i;
    }
    
    return ans
};