摘要

此文是筆者在解 LeetCode Problems: 1. Two Sum 的過程。雖然這題很簡單,但看了 LeetCode 的 tags(相當於提示)才知道可以用 Hash Table 之類的關聯式容器來進一步優化成 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, and you may not use the same element twice.

Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,

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

中譯

給定一個整數陣列,回傳兩個索引,這兩個元素加起來必須等於指定目標。

你得假設每一組輸入只會有一組解,且陣列元素不可重複使用。

範例:

1
2
3
4
給定 nums = [2, 7, 11, 15], target = 9,

因為 nums[0] + nums[1] = 2 + 7 = 9
回傳 [0, 1].

參考解法

方法一

思路

直觀來說,兩數相加等於目標值,因此簡單遍歷兩次陣列就可以得出結果。

由於不能重複使用元素的關係。因此,

第一次遍歷的最後一個元素可以跳過,因為第二次遍歷會用到,所以第一個迴圈只需要跑 n - 1 次。

第二次遍歷時,由於第一次遍歷已跑了 i 個,因此第二次遍歷從第 i + 1 個開始跑即可。

此解法的時間複雜度為 O(n^2)。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
std::vector<int> twoSum(std::vector<int>& nums, int target)
{
auto size = nums.size();
auto firstSize = size - 1;
for (auto i = 0; i != firstSize; ++i) {
for (auto j = i + 1; j != size; ++j) {
if (nums[i] + nums[j] == target) {
return std::vector<int> {i, j};
}
}
}
return std::vector<int>();
}
};

方法二

思路

為了減少時間複雜度,有些運算其實可以在一邊遍歷一邊運算時就保存起來。

已知 target = nums[i] + xtarget - nums[i] = x

此時可以用關聯式容器(map, table, dictionary 等)將 nums[i]i 存起來,nums[i] 為 key,i 為 value。

如果 x 存在於 map,代表 x 曾被遍歷過 ,此時的 x 及現在的 nums[i] 加起來等於 target,回傳 x 的 index(從 map 取出)及 i 即為答案。

此解法的時間複雜度為 O(n)。

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
std::vector<int> twoSum(std::vector<int>& nums, int target)
{
auto size = nums.size();
auto map = std::map<int, int>(); // <num, index>
for (auto i = 0; i != size; ++i) {
auto num = nums[i];
auto diff = target - num;
if (map.find(diff) != map.end()) {
return std::vector<int> {map[diff], i};
}
map[num] = i;
}
return std::vector<int>();
}
};