#1.Two Sum
Problem statement
Given an array of integers nums
and an integer target
, return indices of the two numbers such that they add up to target
.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.
Example 1
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
Example 2
Input: nums = [3,2,4], target = 6
Output: [1,2]
Example 3
Input: nums = [3,3], target = 6
Output: [0,1]
Explanation
從給定的 array
中找到兩個數相加等於 target
,並且返回兩數索引
- 只會有一個有效答案
- 同一個元素不會使用兩次
- 可以返回任何順序的索引
Solution
比較直覺地方式是使用雙迴圈迭代陣列來解,這種暴力解法遇到資料量較大時,需要更多時間來完成。
如果以時間複雜度作為考量,需設法減少迴圈的使用次數,讓執行時間大幅下降,那麼可使用一個額外空間來儲存元素,以達到空間換時間的想法,雖然此方法讓時間複雜度降低,同時也提高了空間複雜度。
Array
透過雙迴圈逐一走訪陣列,因為元素不可重複,故取 i+1 略過自己以及計算過的值
public int[] TwoSum(int[] nums, int target)
{
int i, j;
for (i = 0; i < nums.Length; i++)
for (j = i + 1; j < nums.Length; j++)
if (nums[i] + nums[j] == target)
return new int[] { i, j };
return null;
}
HashTable
使用一個額外空間 HashTable
,以達到用空間換取時間
public int[] TwoSum(int[] nums, int target)
{
Hashtable hash = new Hashtable();
for (int i = 0; i < nums.Length; i++)
{
int num = nums[i];
int diff = target - num;
if (hash.ContainsKey(diff))
return new int[] { i, (int)hash[diff] };
if (!hash.ContainsKey(num))
hash.Add(num, i);
}
return null;
}
Dictionary
一樣使用一個額外空間 Dictionary
達到空間換時間的目的
public int[] TwoSum(int[] nums, int target)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int num = nums[i];
int diff = target - num;
if (dic.ContainsKey(diff))
return new int[] { i, (int)dic[diff] };
if (!dic.ContainsKey(num))
dic.Add(num, i);
}
return null;
}
Reference
Thanks for reading the article 🌷 🌻 🌼
If you like it, please don't hesitate to click heart button ❤️
or click like on my Leetcode solution
or follow my GitHub ⭐
or buy me a coffee ⬇️ I'd appreciate it.
Top comments (0)