#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)