【1日1本LeetCode】#1 Two Sum
3508 ワード
1日1本のLeetCodeシリーズ
(一)テーマ
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: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.
テーマの意味は:1組の配列と1つの目標値を入力して、配列の中で2つの数を探し出して、彼らの和は目標値に等しくて、2つの数の下の記号を返します.
(二)コード実装
最初にテーマを見ると、私たちはすぐに以下の答えを得ることができます.
このような解法の時間的複雑度はO(N^2)であり,コードをコミットするとTime Limit Exceededを誤報する.時間が超過する.
別の方法では,ハッシュテーブル検索の時間的複雑さはO(1)であることを知っており,ここではハッシュテーブル検索を用いて時間的複雑さをO(n)に低減することができる.
(一)テーマ
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: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. UPDATE (2016/2/13): The return format had been changed to zero-based indices. Please read the above updated description carefully.
テーマの意味は:1組の配列と1つの目標値を入力して、配列の中で2つの数を探し出して、彼らの和は目標値に等しくて、2つの数の下の記号を返します.
(二)コード実装
最初にテーマを見ると、私たちはすぐに以下の答えを得ることができます.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> result;
for(int i = 0 ; i < nums.size() ; ++i)
{
for(int j = i+1 ; jif(nums[i]+nums[j] == target)
{
result.push_back(i);
result.push_back(j);
return result;
}
}
}
}
};
このような解法の時間的複雑度はO(N^2)であり,コードをコミットするとTime Limit Exceededを誤報する.時間が超過する.
別の方法では,ハッシュテーブル検索の時間的複雑さはO(1)であることを知っており,ここではハッシュテーブル検索を用いて時間的複雑さをO(n)に低減することができる.
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int ,int> map;
vector<int> result;
for(int i = 0 ; i < nums.size() ; ++i)
{
if(map.find(target - nums[i])!=map.end())
{
if(map[target - nums[i]]!=i)
{
result.push_back(map[target - nums[i]]);
result.push_back(i);
return result;
}
}
map[nums[i]] = i;
}
}
};