LeetCode-01-Two Sum

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 中添加元素，容量通过重新分配按需自动增加。

LeetCode-01-Two Sum