1、两数之和
2020-01-08 16:02:39来源:博客园 阅读 ()
1、两数之和
题目:
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
答案:
1)暴力破解,遍历每个元素 x,并查找后面是否存在一个值与 target−x 相等的目标元素。缺点:时间复杂度高
1 class Solution { 2 public int[] twoSum(int[] nums, int target) { 3 for (int i = 0; i < nums.length; i++) { 4 for (int j = i + 1; j < nums.length; j++) { 5 if (nums[j] == target - nums[i]) { 6 return new int[] { i, j }; 7 } 8 } 9 } 10 throw new IllegalArgumentException("No two sum solution"); 11 } 12 }View Code
2)通过循环遍历两次哈希表,第一次添加全部元素,第二次通过减去元素,查找另外一个是否在哈希表里面。
1 class Solution { 2 public int[] twoSum(int[] nums, int target) { 3 Map<Integer, Integer> map = new HashMap<>(); 4 for (int i = 0; i < nums.length; i++) { 5 map.put(nums[i], i); 6 } 7 for (int i = 0; i < nums.length; i++) { 8 int complement = target - nums[i]; 9 if (map.containsKey(complement) && map.get(complement) != i) { 10 return new int[] { i, map.get(complement) }; 11 } 12 } 13 throw new IllegalArgumentException("No two sum solution"); 14 } 15 }View Code
3)循环遍历一次哈希表,每插入一个元素,查看哈希表里面是否含有目标元素,及是否含有target-x,具体上代码:
1 class Solution { 2 public int[] twoSum(int[] nums, int target) { 3 Map<Integer, Integer> map = new HashMap<>(); 4 for (int i = 0; i < nums.length; i++) { 5 int complement = target - nums[i]; 6 if (map.containsKey(complement)) { 7 return new int[] { map.get(complement), i }; 8 } 9 map.put(nums[i], i); 10 } 11 throw new IllegalArgumentException("No two sum solution"); 12 } 13 }View Code
原文链接:https://www.cnblogs.com/-nbloser/p/12164498.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- powerdesigner两数据库对比 2020-01-19
- 一些算法题及答案 2019-03-01
- LeetCode每天一题之两数之和 2018-12-19
- Java输入输出入门 A+B 2018-11-29
- 数据的运算,求和,两数求最大,三数求最大,两数是否相等 2018-11-22
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash