欢迎访问宙启技术站
智能推送

编写一个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为要输出的数组。