概述
作为简单题的第一题(Two Sum)，简答来说就是给出一个序列以及目标值，求出能加和出目标值的两个数字在数组中的下标。
分析
这个题目可以说是一目了然，直接能够想到的解法就是遍历这一个序列，然后遍历下标大于当前遍历到的数字的元素，如果有匹配的数字就直接返回结果即可。
如果单纯遍历，时间复杂度高达O(n2)，这个复杂度不太令人满意。
那么是否可以通过空间换时间呢？自然是没问题的。
后续考虑通过使用HashMap的方式记录每个值对应的元素的下标，每次检查是否有当前值相加得到目标值的的key存在，将时间复杂度降低到了O(n)，不过空间复杂度也上升到了O(n)。
解法
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
public class Solution { public int[] twoSum(int[] nums, int target) { Map<Integer, Integer> numIdxMap = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; ++i) { numIdxMap.put(nums[i], i); } int[] idx = new int[2]; for (int i = 0; i < nums.length; ++i) { if (numIdxMap.containsKey(target - nums[i])) { int j = numIdxMap.get(target - nums[i]); if (i == j) { continue; } idx[0] = i; idx[1] = j; if (idx[0] > idx[1]) { int tmp = idx[1]; idx[1] = idx[0]; idx[0] = tmp; } break; } } return idx; } } |