前言:
目前大家对“java输入两个整数求之间的和”大体比较注重,大家都想要剖析一些“java输入两个整数求之间的和”的相关资讯。那么小编同时在网络上汇集了一些有关“java输入两个整数求之间的和””的相关资讯,希望咱们能喜欢,兄弟们一起来学习一下吧!给定一个整数数组和一个目标值,找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用。即:每个index上的数字只能用一次。
示例
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
解答
这个题目的原题是在:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台 网站上能找到。
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 示例 1:输入:nums = [2,7,11,15], target = 9输出:[0,1]解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。示例 2:输入:nums = [3,2,4], target = 6输出:[1,2]示例 3:输入:nums = [3,3], target = 6输出:[0,1] 提示:2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109只会存在一个有效答案 进阶:你可以想出一个时间复杂度小于 O(n2) 的算法吗?
完整的题目要求如上。
应该对所有人第一次想到的就是使用 2 个 For 循环吧。
for (int i = 0; i < nums.length; i++) { for (int j = i + 1; j < nums.length; j++) { if (nums[j] == target - nums[i]) { log.debug("{}", new int[]{i, j}); } } }
然后从 2 个 for 循环中获得下标列表,最后 break 循环就可以了。
进阶问题
如何让我们只使用 1 个 for 循环的情况下解决这个问题。
这个时候我们就需要使用 HashMap 了。
首先,我们把数据放入到 HashMap 中。
然后取第一个元素,当取得第一个元素后,再用和减去第一个元素,这个得到的值为另外一个元素。
然后拿着这个元素到 HasMap 中去找,如果找到了就返回,如果没找到就继续去获得下一个元素。
然后再拿和去减去获得的第二个元素后再到 Map 中去找。
Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement) && map.get(complement) != i) { log.debug("{}", new int[]{i, map.get(complement)}); } }用一个 Map 解决
还有一个更高的效率,就是在循环一次,然后用 Map 解决。
在上面的解决方案中,我们在对 HashMap 遍历了 2 次,第一次是构建 Map,第二次是从 Map 中查找。
能不能我们在构建的时候就完成操作。
答案是肯定的。
于是,我们就有了下面的代码:
Map<Integer, Integer> map2 = new HashMap<>(); for (int i = 0; i < nums.length; i++) { int complement = target - nums[i]; if (map.containsKey(complement)) { log.debug("{}", new int[]{map2.get(complement), i}); } map2.put(nums[i], i); }
上面的代码在 HashMap 构建的时候就进行判断,把和减掉当前的值,如果我们的 Map 中能够找到这个值,我们就返回。
如果不能找到就添加到 Map 中。
总结
如果不考虑效率的方法,第一个方法就可以解决问题了。
这个没有什么难度。
如果需要考虑效率的话,重构数据结构,通常是比较有效的方法,Java 中用得比较多的是 Map,因为 Map 通常能够存储更多的信息,而且遍历效率高。
我们对一些问题,如果算法不太好弄的话,通常考虑的是能不能给它们换个数据结构,比如说 List ,Map 呀这种的。
个人感觉这个题目在算法中是属于比较简单的题目,但是不同的解法可能会比较多。
整体感觉还是不错的,没有像一些算法题目,一上来就给你一个下马威,你完全都没有想明白数据结构应该怎么存。然后后面的逻辑就会越来越混乱。
标签: #java输入两个整数求之间的和