LeetCode 1. Two Sum 解题报告

43 阅读 0 评论 29 点赞

我是靠谱客的博主拉长白昼，最近开发中收集的这篇文章主要介绍LeetCode 1. Two Sum 解题报告，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题意：

数组nums中，有两个元素的和是target，找出这两个元素的位置。

思路：

维护一个map，用数组的元素的值做key，用元素的位置做value。遍历nums，对每个num来说，如果map[target - num] 有值的话，就返回map[target - num]和num的位置，如果没有找到的话，就把num插入到map中，map[num] = index。时间复杂度O(nlogn)。

C++ Code:

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::map<int, int> map;
for(int i = 0; i < nums.size(); i++)
{
if(map.find(target - nums[i]) != map.end())
{
std::vector<int> result{map[target - nums[i]], i + 1};
return result;
}
map[nums[i]] = i + 1;
}
}
};

Python Code:

class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
map = {}
for index,num in enumerate(nums):
if target - num in map:
return [map[target - num], index + 1]
map[num] = index + 1

JS Code:

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