1.Two Sum
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].
譯文
提供一個(gè)整數(shù)數(shù)組， 返回?cái)?shù)組的兩個(gè)序號(hào)，使得它們加起來達(dá)到特定的目標(biāo)。
您可以假設(shè)每個(gè)輸入都有一個(gè)解決方案,并且您不能使用相同的元素兩次。
標(biāo)簽：Array,Hash Table
數(shù)據(jù)結(jié)構(gòu)
數(shù)組
Hashtable
解法
1.循環(huán)暴力求解
public class Solution {
public int[] TwoSum(int[] nums, int target) {
for (int i = 0; i < nums.Length; i++)
{
for (int j = 0; j < nums.Length; j++)
{
if(i != j)
{
if (nums[i] + nums[j] == target)
{
int[] re = { i, j };
return re;
}
}
}
}
return null;
}
}
嘗試算法復(fù)雜度：O(n * n) = O(n^2)
這種辦法 c# 的執(zhí)行效果
2.遞歸解法-這個(gè)不用考慮了，時(shí)間通不過
public class Program
{
public static void Main(string[] args)
{
int[] nums = new int[] { 3, 2, 4 };
(new Solution()).TwoSum(nums,6);
}
}
public class Solution
{
public int target;
public int stt;
public int edd;
public int[] TwoSum(int[] nums, int target)
{
this.target = target;
Addok(nums, 0, 1);
int[] re = { this.stt, this.edd };
return re;
}
public void Addok(int[] nums, int start, int end)
{
if (end == nums.Length)
{
start = start + 1;
if (start >= nums.Length) return;
this.stt = start;
end = start + 1;
}
if ((nums[start] + nums[end]) == target)
{
this.edd = end;
return;
}
Addok(nums, start, end + 1);
}
}
3.參考
這個(gè)我確實(shí)想得太笨了，題中給了兩個(gè)條件，
- 1 是肯定有一組合適
- 2 不能使用相同的元素兩次
參考鏈接給出的是更給力的一種解法，一次循環(huán)，把當(dāng)前數(shù) nums[i] 于 target 的差值，存入
HashTable 中，通過對(duì)比 num[i+1] 和 HashTable 中的的值做 比較，得出結(jié)果
實(shí)際寫了代碼，發(fā)現(xiàn)有兩點(diǎn)沒有注意到的地方
- 邏輯上繞了
- [3,3,2] 這種情況在 寫入的時(shí)候要做判斷，搞得我都沒信心往 HashTable 中寫數(shù)據(jù)了
public class Solution
{
Hashtable table = new Hashtable();
public int[] TwoSum(int[] nums, int target)
{
int i = 0;
for (i = 0; i < nums.Length; i++)
{
if (table.ContainsKey(nums[i]) == true)
{
int[] re = { (int)table[nums[i]], i };
return re;
}
if (table.ContainsKey(target - nums[i]) != true)
{
table.Add(target - nums[i], i);
}
}
return null;
}
}
這個(gè)的執(zhí)行效果就好多了
數(shù)組
在 VSHelp 中對(duì)數(shù)組的定義
- 數(shù)組是一種數(shù)據(jù)結(jié)構(gòu)，它包含若干相同類型的變量
- 數(shù)組是使用類型聲明的：type[] arrayName;
常見數(shù)組的聲明
class TestArraysClass
{
static void Main()
{
// Declare a single-dimensional array
int[] array1 = new int[5];
// Declare and set array element values
int[] array2 = new int[] { 1, 3, 5, 7, 9 };
// Alternative syntax
int[] array3 = { 1, 2, 3, 4, 5, 6 };
// Declare a two dimensional array
int[,] multiDimensionalArray1 = new int[2, 3];
// Declare and set array element values
int[,] multiDimensionalArray2 = { { 1, 2, 3 }, { 4, 5, 6 } };
// Declare a jagged array
int[][] jaggedArray = new int[6][];
// Set the values of the first array in the jagged array structure
jaggedArray[0] = new int[4] { 1, 2, 3, 4 };
}
}
數(shù)組屬性：
- 數(shù)組可以是 一維、 多維或 交錯(cuò) 的。
- 數(shù)值數(shù)組元素的默認(rèn)值設(shè)置為 0 ，而引用元素的默認(rèn)值設(shè)置為 null。
- 交錯(cuò)數(shù)組是數(shù)組的數(shù)組，因此其元素是引用類型并初始化為 null。
- 數(shù)組的索引從零開始：具有 n 個(gè)元素的數(shù)組的索引是從 0 到 n-1。
- 數(shù)組元素可以是任何類型，包括 數(shù)組類型。
- 數(shù)組類型是從抽象基類型 Array 派生的 引用類型。 由于此類型實(shí)現(xiàn)了
IEnumerable和IEnumerable< T>，因此可以對(duì) C# 中的所有數(shù)組使用foreach 迭代。
交錯(cuò)數(shù)組
交錯(cuò)數(shù)組元素的維度和大小可以不同。 交錯(cuò)數(shù)組有時(shí)稱為“數(shù)組的數(shù)組”。int[][,] jaggedArray4 = new int[3][,]
{
new int[,] { {1,3}, {5,7} },
new int[,] { {0,2}, {4,6}, {8,10} },
new int[,] { {11,22}, {99,88}, {0,9} }
};
Hashtable 類
表示根據(jù)鍵的哈希代碼進(jìn)行組織的鍵/值對(duì)的集合
每個(gè)元素都是一個(gè)存儲(chǔ)在 DictionaryEntry 對(duì)象中的鍵/值對(duì)。
| - | - |
|---|---|
| 鍵 | not null |
| 值 | 可為 null |
當(dāng)向 Hashtable 添加元素時(shí)，Hashtable 的實(shí)際加載因子將增加。 當(dāng)實(shí)際加載因子達(dá)到指定的加載因子時(shí)，Hashtable 中存儲(chǔ)桶的數(shù)目自動(dòng)增加到大于當(dāng)前 Hashtable 存儲(chǔ)桶數(shù)兩倍的最小質(zhì)數(shù)。
Hashtable 的容量是 Hashtable 可擁有的元素?cái)?shù)。 隨著向 Hashtable 中添加元素，容量通過重新分配按需自動(dòng)增加。
