问题描述

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, and you may not use the same element twice.

• mode：easy
• tag： array（数组）

暴力解决

对于数组中每个数，遍历后面的数，看是否有满足条件的。

• 时间复杂度：$O(N^2)$
• 空间复杂度: $O(N)$

Python

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
j=i+1
while(j<len(nums)):
if (nums[j] == target - nums[i]):
return [i,j]
j=j+1

c++

class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
int nums_size = nums.size();
vector<int> res;
for(int i=0; i<nums_size; i++)
{
for(int j=i+1; j<nums_size; j++)
{
if(nums[j]==target-nums[i])
{
res.push_back(i);
res.push_back(j);
}
}
}
return res;
}
};

利用哈希表

对于nums[i]，看target-nums[i]是否在哈希表中，若在，返回两数索引，否则，将nums[i]加入哈希表。

• 时间复杂度: $O(N)$
• 空间复杂度: $O(N)$

Python

利用dict

class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
dict={}
for i in range(len(nums)):
sub = target - nums[i]
if sub in dict:
return [dict[sub],i]
else:
dict[nums[i]]=i

C++

利用unordered_map

class Solution
{
public:
vector<int> twoSum(vector<int> &nums, int target)
{
//Key是数字，value是该数字的index
unordered_map<int, int> hash;
vector<int> result;
int numsSize = int(nums.size());
for (int i = 0; i < numsSize; i++)
{
int numberToFind = target - nums[i];
//如果找到numberToFind，就return
if (hash.find(numberToFind) != hash.end())
{
result.push_back(hash[numberToFind]);
result.push_back(i);
return result;
}
//如果没有找到，把该数字的index放到hash表中
hash[nums[i]] = i;
}
return result;
}
};

最后

以上就是鳗鱼毛豆为你收集整理的两数之和 Two Sum问题描述暴力解决利用哈希表的全部内容，希望文章能够帮你解决两数之和 Two Sum问题描述暴力解决利用哈希表所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。