leetcode-1-Two-Sum

发表于   |  

描述

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
4
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析

用哈希表，存储值，以及对应的下标，通过 target 找到某个数字应该对应的值，如果在哈希表中找到这个值，返回这一对。

解决方案1(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> value_index_map;
        vector<int> result;
        for(int i = 0; i < nums.size(); i++) {
            value_index_map[nums[i]] = i;
        }
        
        for(int i = 0; i < nums.size(); i++) {
            int now_pair = target - nums[i];
            if(value_index_map.find(now_pair) != value_index_map.end() && value_index_map[now_pair] > i) {
                result.push_back(i);
                result.push_back(value_index_map[now_pair]);
            }
        }
        return result;
    }
};

解决方案2(Python)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        value_index_map = {}
        for index, value in enumerate(nums):
            value_index_map[value] = index
            
        for index, value in enumerate(nums):
            if target-value in value_index_map:
                index2 = value_index_map[target-value]
                if index != index2:
                    return index, index2

解决方案3(Golang)

1
2
3
4
5
6
7
8
9
10
func twoSum(nums []int, target int) []int {
    mapping := make(map[int]int)
    for index_i, value := range nums {
        if index_j, got_it := mapping[value]; got_it {
            return []int{index_i, index_j}
        }
        mapping[target-nums[index_i]] = index_i
    }
    return nil
}

解决方案4(Ruby) 2017-05-27

1
2
3
4
5
6
7
8
9
10
11
12
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
    map = {}
    
    nums.each_with_index do |num, idx|
        i = map[num]
        return [i, idx] if i
        map[target-num] = idx
    end
end

解决方案5(Javascript) 2018-11-11

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 = [];
    var 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;
};

解决方案5(Rust) 2019-2-3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
use std::collections::HashMap;

impl Solution {
    pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
        let mut map = HashMap::with_capacity(nums.len());
        for (index, num) in nums.iter().enumerate() {
            match map.get(&(target - num)) {
                None => { map.insert(num, index); },
                Some(sub_index) => { return vec![*sub_index as i32, index as i32]}
            }
        }
        vec![]
    }
}

相关问题

题目来源