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# 的执行效果

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 派生的 引用类型。 由于此类型实现了 IEnumerableIEnumerable< 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 中添加元素,容量通过重新分配按需自动增加。

关于算法的复杂度

经典的总结 算法时间复杂度的计算

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 203,362评论 5 477
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 85,330评论 2 381
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 150,247评论 0 337
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 54,560评论 1 273
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 63,580评论 5 365
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,569评论 1 281
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 37,929评论 3 395
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,587评论 0 258
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 40,840评论 1 297
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,596评论 2 321
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,678评论 1 329
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,366评论 4 318
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 38,945评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 29,929评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,165评论 1 259
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 43,271评论 2 349
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,403评论 2 342

推荐阅读更多精彩内容

  • 题目要求 Given an array of integers, return indices of the tw...
    SiyueLin阅读 361评论 0 0
  • logke阅读 269评论 1 0
  • 背景 一年多以前我在知乎上答了有关LeetCode的问题, 分享了一些自己做题目的经验。 张土汪:刷leetcod...
    土汪阅读 12,719评论 0 33
  • 1. Java基础部分 基础部分的顺序:基本语法,类相关的语法,内部类的语法,继承相关的语法,异常的语法,线程的语...
    子非鱼_t_阅读 31,560评论 18 399
  • 春风起兮尘飞扬, 路泥泞兮下村庄。 风带寒意兮沁入骨, 血有悲凉兮自神伤。 思当下兮心迷惘, 望前途兮意彷徨。 翘...
    孑的篮球场阅读 218评论 0 0