如何求得一个数组中和为指定值的2个元素下标?
例:数组num={2, 7, 17, 26, 27, 31, 41, 42, 55, 80} target=72.求得元素下标值为:{5,6}
首先分析一下:
1. 这个数组并不是有序数组,这就排除了搜索空间缩减方法.有序数列查找方式可以参考如何从有序数组中找到和为指定值的两个元素下标
2. 如果使用暴力遍历方式,那时间复杂度会是O(n^2),有些大,需要换种思路,减少时间复杂度.
3. 要找到对应元素下标,不是元素值,所以使用排序方式,会打乱原有下标值.
整理下思路,因为数组是无序的,所以想知道两数之和是指定值,必须要遍历数组,那时间复杂度,至少会是O(n);
遍历到一个数时,另一个数也可以根据x=target-n计算出来,那问题焦点转换为判断另一数是否存在于数组中,遍历过的,我们不想重新遍历,需要合理的数据结构记录下;未遍历过的,可以在遍历到时,再次使用这条规则.
什么样的数据结构适合呢?
哈希结构! 时间复杂度为O(1).
根据这个思路,我们看下代码:
int[] sum2Num(int[] nums, int target) {
int length = nums.length;
Map<Integer, Integer> map = new HashMap<>(length);
for (int i = 0; i < length; i++) {
Integer n = nums[i];
Integer otherNum = target - n;
if (map.containsKey(otherNum)) {
// bingo
return new int[]{i, map.get(otherNum)};
}
map.put(n, i);
}
return new int[]{};
}
总结一下,使用map结构是空间换时间,提升时间复杂度.