本文主要是介绍leetcode第一道题，找出数组中两数之和为target的两个数，返回其下标答案及思考，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
初始函数
class Solution {public int[] twoSum(int[] nums, int target) {}
}
思路解析
- 最好想的就是暴力法，拿第一个和第二个、第三个、第四个加和是不是等于target，然后再用第二个和第三个、第四个、第五个等等依次加和，时间复杂度，很简单两个for循环，n²级别。
public int[] twoSum(int[] nums, int target) {for (int i = 0; i < nums.length; i++) {for (int j = i + 1; j < nums.length; j++) {if (nums[j] == target - nums[i]) {return new int[] { i, j };}}}throw new IllegalArgumentException("No two sum solution");
}
- 用hash表来做：首先将所有数组元素放到hash表中，然后再监测是否含有每个元素的差值？（注意：存储数组元素为键key，因为有containsKey（）方法存取比较简单，containsValue（）比较麻烦）
public int[] twoSum(int[] nums, int target) {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) {return new int[] { i, map.get(complement) };}}
}
- 改进的思路：
在放入hash表的过程中，就随时监测表中是否有（target-当前值）相关元素。
class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer,Integer> hm = new HashMap<Integer,Integer>();int length = nums.length;int [] result = new int[2];for(int i=0;i<length;i++){if(hm.containsKey(target-nums[i])) {result[0] = hm.get(target-nums[i]);result[1] = i;break;}hm.put(nums[i], i);}return result;}}
思考题：
- hashMap取元素是怎么取的？根据key的hash值定位到table的表头，如果发现hash冲突，则根据链表来逐个比较值。只不过时间复杂度从o(1)上升到o（N）。
- hashMap中containsKey是怎么判断的？
public boolean containsKey(Object key) {return getNode(hash(key), key) != null;}
final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))return first;if ((e = first.next) != null) {if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);do {if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}return null;}
这篇关于leetcode第一道题，找出数组中两数之和为target的两个数，返回其下标答案及思考的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
