题目链接:
两数之和
分析:
1. 如果一层一层遍历的话,比较麻烦,时间复杂度是O(n^2),采用下面的方法会更好一些,时间复杂度为O(n)
2. 可以借助HashMap,把每一次查找的元素都放在map中
3. 目前遍历的数假设是A,那么实现目标的另一个数字 B 应满足 B = Target - A
4. 当你遍历的时候,如果在map中可以找到 A 对应的 B,那么直接就把 A 和 B的下标输出就可以了;
如果遍历 A 的时候,找不到对应的 B,就把 A 的元素和 A 的下标以K-V键值对的形式存进map中,继续向后遍历,直到找到一组满足题意的 A和B
代码实现如下:
public class TwoSum {
public int[] twoSum(int[] nums,int target) {
int[] res = new int[2];
if (nums == null || nums.length <= 1)
return res;
HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
// 从第一个数开始遍历
for (int i = 0;i < nums.length;i++) {
int num = nums[i];
int val = target - num; // 用 target减去目前的数
// 如果 map中有 target减去当前数的那个数
if (map.containsKey(val)) {
// 把当前数num的下标,val的下标返回给 建立的数组 res
res[0] = i;
res[1] = map.get(val);
return res;
}
// 表示当前 map中没有target减去当前数的那个数val,
// 就把当前数 num和它的index添加到 map中
else
map.put(num,i);
}
return res;
}
}