你的位置:首页 > ASP.net教程

[ASP.net教程]一个非常简单的算法题是否愿意挑战一下呢


 求两个数之和。这个问题够简单吧!能做对绝对不是问题,问题是你是否能做的比较好。好了,请看题目:

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].

看了题目之后,心中是否已经有了答案。很简单蛮力法嘛,一个双循环就可以搞定了。但是有没有更好一点的方法呢?
如果你已经想到了也没必要往下看了。

如果你还没有什么头绪,那么稍微往HashTable想想,估计你们也想到了。其实也是很简单,只是有时候想问题的方向不对,就老是想不到点子上罢了。如果还没想到的话,就往下看一下吧!

相比较于,用一个双循环,在时间效率上面可能不是很好。那么久可以很容易想到,也经常听到的“空间换时间”,就是这样,我们可以使用一个字典键值对保存中间值,减少一次循环,变成单循环,那么时间效率就可以得以提升。那么这个字典到底保存什么呢?保存目标值减去当前数组的整数值(键)和数组整数值的下标(值)。当我们执行循环时,每循环到一个数组中的整数,我们就判断这个整数是否是字典中的键,如果不是我们就按照前面说的键值存入字典中,题目说了有且只有一对数字是符合条件的,那么也就不用考虑重复键了。如果是,我们就找到了这两个整数,接着就是返回整两个整数的下标了。第一个整数的下标就是当前字典的键对应的值,第二个整数的下标就是当前循环到的i值。就是这么简单!如果我说的不够清楚就直接看代码。

以下是C#的实现:
 1 using System; 2 using System.Collections.Generic; 3  4 namespace XiaoLiang 5 { 6   public class TwoSum 7  { 8     public int[] TwoSum(int[] nums, int target) 9   {10       int[] result = new int[2];11       Dictionary<int, int> dictionary = new Dictionary<int, int>();12       for (int i = 0; i < nums.Length; i ++ )13    {14         if(dictionary.ContainsKey(nums[i]))15    {16           result[0] = dictionary[nums[i]];17           result[1] = i;18           return result;19    }20         else21    {22           dictionary.Add(target - nums[i] , i);23    }24   }25       return result;26  }27  }28 }




如果有什么说的不对的地方欢迎拍砖,有更好的方法可以共享。