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].
译文
提供一个整数数组， 返回数组的两个序号，使得它们加起来达到特定的目标。
您可以假设每个输入都有一个解决方案,并且您不能使用相同的元素两次。
标签：Array,Hash Table
数据结构
数组
Hashtable
解法
1.循环暴力求解
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;
}
}
尝试算法复杂度：O(n * n) = O(n^2)
这种办法 c# 的执行效果
2.递归解法-这个不用考虑了，时间通不过
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.参考
这个我确实想得太笨了，题中给了两个条件，
- 1 是肯定有一组合适
- 2 不能使用相同的元素两次
参考链接给出的是更给力的一种解法，一次循环，把当前数 nums[i] 于 target 的差值，存入
HashTable 中，通过对比 num[i+1] 和 HashTable 中的的值做 比较，得出结果
实际写了代码，发现有两点没有注意到的地方
- 逻辑上绕了
- [3,3,2] 这种情况在 写入的时候要做判断，搞得我都没信心往 HashTable 中写数据了
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;
}
}
这个的执行效果就好多了
数组
在 VSHelp 中对数组的定义
- 数组是一种数据结构，它包含若干相同类型的变量
- 数组是使用类型声明的：type[] arrayName;
常见数组的声明
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 };
}
}
数组属性：
- 数组可以是 一维、 多维或 交错 的。
- 数值数组元素的默认值设置为 0 ，而引用元素的默认值设置为 null。
- 交错数组是数组的数组，因此其元素是引用类型并初始化为 null。
- 数组的索引从零开始：具有 n 个元素的数组的索引是从 0 到 n-1。
- 数组元素可以是任何类型，包括 数组类型。
- 数组类型是从抽象基类型 Array 派生的 引用类型。 由于此类型实现了
IEnumerable和IEnumerable< T>，因此可以对 C# 中的所有数组使用foreach 迭代。
交错数组
交错数组元素的维度和大小可以不同。 交错数组有时称为“数组的数组”。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 类
表示根据键的哈希代码进行组织的键/值对的集合
每个元素都是一个存储在 DictionaryEntry 对象中的键/值对。
| - | - |
|---|---|
| 键 | not null |
| 值 | 可为 null |
当向 Hashtable 添加元素时，Hashtable 的实际加载因子将增加。 当实际加载因子达到指定的加载因子时，Hashtable 中存储桶的数目自动增加到大于当前 Hashtable 存储桶数两倍的最小质数。
Hashtable 的容量是 Hashtable 可拥有的元素数。 随着向 Hashtable 中添加元素，容量通过重新分配按需自动增加。
