LeetCode #1 Two Sum
原题:
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].
技巧学习:
HashMap的运用
暴力方法解:
注意:
1)import java小写,Arrays.sort(数组名),但这题不用,因为要按数据顺序返回,故不能用排序。
2)数组的length没有括号
3)return new int[] {I ,j}
Time Complexity: O(n^2)
Space Complexity: O(1)
O(n)的方法:
当时想到用HashMap将数据和位置一一对应,但没有深入想下面的步骤/是否可行。
问题:碰到相同的数字怎么办?
解决:HashMap不允许相同的键值,但允许相同的value。将index作为键值,数据作为value?
问题:无法根据value取得key。
解决:使用put方法时如遇到相同键值会覆盖value。由于是顺序查找,一旦有数据个数大于1,先遇到的数的index一定与最后存储在map中的不同。
注意:
Map<Integer, Integer> map= new HashMap<>(); 的定义
Throw an exception makes more sense than return null.
Time Complexity: O(n)
Space Complexity: O(n)
第三种解法
官方给出第三种解法与第二种类似,但是只顺序查找数组一次,即一边查complement一边put。
做下面一题时突然考虑到return value的顺序问题。若要求按大小输出:
1)用第二种顺序查找的话,一定是i, get(comp)。(假如get(comp)<I,会先返回)
2)用第三种的话,一定是get(comp), i。(comp不可能是后面还未放进map的)