外贸专业网站建设,品牌设计公司排名广州设计,WordPress只能ssl,网站建设与网站优化问题描述
给定一个整数数组 nums 和一个目标值 target#xff0c;请你在该数组中找出和为目标值的那 两个 整数#xff0c;并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是#xff0c;你不能重复利用这个数组中同样的元素。
Given nums [2, 7, 11, 15…问题描述
给定一个整数数组 nums 和一个目标值 target请你在该数组中找出和为目标值的那 两个 整数并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是你不能重复利用这个数组中同样的元素。
Given nums [2, 7, 11, 15], target 9,
Because nums[0] nums[1] 2 7 9,
return [0, 1].
Solution public static int[] twoSum(int[] nums, int target) {MapInteger, Integer map new HashMap();// 建立值与下标对应关系for(int i 0; inums.length; i){map.put(nums[i], i);}// 获取键集合int[] arr new int[2];for(int i 0; i nums.length; i){int complement target - nums[i];if(map.containsKey(complement) map.get(complement) ! i){arr[0] i;arr[1] map.get(complement);}}return arr;}
对于输入为[ 3, 3 ]target 6 的测试case我们要如何理解
首先在Map 中相同的key 如果存在那么旧的key 对应的 值就会被覆盖掉第一个 for 循环结束后map 中只有一个键值对即{ 3 1 }这并不会影响结果只不过在 arr[0] 赋值的时候需要注意一定不要使用 arr[0] map.get(nums[i]); 这种写法看似与上面的正确解法语义上相同但是却忽视了相同元素被覆盖掉的情况。
总结
上段代码引用了LeetCode上此问题支持率最高的解决方法。
看到题目的时候我是正常的用了二重for循环进行求解的在LeetCode中也有我那种解法他们称之为Brute Force。
而上面贴出来的这种解法思路在于考虑到了时间复杂度。这里又不得不记录一下我收集到了对时间复杂度的理解 基本操作执行次数与问题规模n成正比。 时间复杂度 共有八个同数量级分别是1log2nnn log2nn^2n^32^nn! 从 1 到 n! 时间复杂度依次增高。二重for循环记作O(n^2)三重for循环记作O(n^3)依此类推。 解释是这样的To improve our run time complexity, we need a more efficient way to check if the complement exists in the array. If the complement exists, we need to look up its index. What is the best way to maintain a mapping of each element in the array to its index? A hash table.
为了改进我们运行时间的复杂程度我们需要更有效的方法去array中检查是否有一个特定的“补足数”存在如果存在我们就去找他的index。那么维护数组元素与其下标之间的映射关系最好的途径是什么呢没错就是 hash 表。
这句话给我的印象特别深。那么如果下一次又出现一个问题要求我们找到两组值的对应关系的话我们首先就会考虑到哈希表。这正是我希望得到的东西一种思考的方向。
We reduce the look up time from O(n) to O(1) by trading space for speed. A hash table is built exactly for this purpose, it supports fast look up in near constant time. I say near because if a collision occurred, a look up could degenerate to O(n) time. But look up in hash table should be amortized O(1) time as long as the hash function was chosen carefully.
我们通过牺牲空间换取速度的方式来将时间复杂度从O(n)到O(1)。哈希表的建立正是为此目的它支持在近乎不变的时间内快速查找。
