您现在的位置是:首页 > 文章详情

算法题丨Two Sum

日期:2018-04-07点击:294

描述

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, and you may not use the same element twice.

示例

Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

算法分析

难度:低
分析:要求给定的数组,查找其中2个元素,满足这2个元素的相加等于给定目标target的值。
思路:一般的思路,我们遍历数组元素,假设当前遍历的数组元素x,再次遍历x之后的数组元素,假设当前再次遍历的数组元素y,判断x+y是否满足target,如果满足,则返回x,y下标,否则继续遍历,直至循环结束。考虑这种算法的时间复杂度是O (n²),不是最优的解法。
跟前面几章类似,我们可以考虑用哈希表来存储数据,这里用C#提供的Hashtable来存储下标-对应值(key-value)键值对;
接着遍历数组元素,如果目标值-当前元素值存在当前的Hashtable中,则表明找到了满足条件的2个元素,返回对应的下标;
如果Hashtable没有满足的目标值-当前元素值的元素,将当前元素添加到Hashtable,进入下一轮遍历,直到满足上一条的条件。

代码示例(C#)

public int[] TwoSum(int[] nums, int target) { var map = new Hashtable(); ; for (int i = 0; i < nums.Length; i++) { int complement = target - nums[i]; //匹配成功,返回结果 if (map.ContainsKey(complement)) { return new int[] { (int)map[complement], i }; } map.Add(nums[i], i); } return null; } 

复杂度

  • 时间复杂度O (n).
  • 空间复杂度O (1).

附录

img_8f0a90f3cbaa0e044fb8bf7b13c4317b.jpe

文章作者:原子蛋
文章出处:https://www.cnblogs.com/lizzie-xhu/
个人网站:https://www.lancel0t.cn/
个人博客:https://blog.lancel0t.cn/
微信公众号:原子蛋Live+
扫一扫左侧的二维码(或者长按识别二维码),关注本人微信公共号,获取更多资源。
本文版权归作者和博客园共有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

原文链接:https://yq.aliyun.com/articles/619976
关注公众号

低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。

持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。

转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。

文章评论

共有0条评论来说两句吧...

文章二维码

扫描即可查看该文章

点击排行

推荐阅读

最新文章