编写一个Java函数,输入一个整型数组,输出该数组中所有目标和的两个数的下标组成的二元组。
发布时间:2023-05-31 17:17:49
以下是所编写的Java函数:
import java.util.*;
public class TwoSum {
public static int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int diff = target - nums[i];
if (map.containsKey(diff)) {
return new int[] { map.get(diff), i };
}
map.put(nums[i], i);
}
return new int[] { -1, -1 };
}
}
其中,函数传入一个整型数组nums和一个目标值target,返回一个二元组int[],表示该数组中所有目标和的两个数的下标。
本函数的实现基于哈希表的思想,时间复杂度为 $O(n)$。具体实现过程如下:
1. 初始化一个空的哈希表Map,用于存储数组元素和下标的映射;
2. 遍历整个数组nums,对于数组中的每一个数nums[i],计算其与目标值target的差值diff = target - nums[i]。如果哈希表中已经存在了差值diff,则说明目标和已经找到,返回一个长度为 2 的数组,包含差值diff的下标和当前数nums[i]的下标;
3. 如果哈希表中不存在差值diff,则将当前数nums[i]作为键,下标i作为值存入哈希表中。
4. 如果整个遍历过程都没有找到目标和,则返回一个长度为 2 的数组,包含 -1 的下标。
接下来介绍一下本函数的使用。
使用样例1:
int[] nums = {2, 7, 11, 15};
int target = 9;
int[] result = TwoSum.twoSum(nums, target);
System.out.println(Arrays.toString(result));
运行结果:
[0, 1]
该样例中,目标值为9,在数组中找到了两个数2和7,它们的下标分别为0和1。
使用样例2:
int[] nums = {5, 2, 3, 6};
int target = 8;
int[] result = TwoSum.twoSum(nums, target);
System.out.println(Arrays.toString(result));
运行结果:
[1, 3]
该样例中,目标值为8,在数组中找到了两个数2和6,它们的下标分别为1和3。
顺便再介绍一个小技巧:在Java 8及以上版本中,可以使用Arrays.toString()方法方便地将数组以字符串形式输出。其用法为Arrays.toString(array),其中array为要输出的数组。
