无序可重复数组中所有两个数相加等于一个固定数的下标组合

题目描述

给定一个无序可重复数组nums，一个固定数k。返回数组中所有两个数相加等于这个固定数的下标组合。例如：数组[3,3,1,5]，固定数为8，返回[0,3]，[1,3]。

思路

暴力双重遍历复杂度太高，用哈希表O(1)的快速查找特性进行内部循环的代替。哈希表存储key为数组值nums[i]，value为数组值出现的下标集合List。

java代码

public static int[][] function(int[] nums,int k){
HashMap<Integer, ArrayList<Integer>> map = new HashMap<>();
ArrayList<int[]> res = new ArrayList<>();
for(int i=0;i<nums.length;i++){
int tmp = k-nums[i];
if(!map.containsKey(tmp)){//如果map里不包含nums[i] - k，则将i添加进value的list中，并更新map
ArrayList<Integer> list = map.get(nums[i])==null?new ArrayList<>():map.get(nums[i]);
list.add(i);
map.put(nums[i],list);
}else{//包含tmp的话，遍历map中tmp的list，制作二元组，加入最终集合res
ArrayList<Integer> list = map.get(tmp);
for (int j=0;j<list.size();j++){
int[] arr = new int[2];
arr[0] = list.get(j);
arr[1] = i;
res.add(arr);
}
}
}
//转成二维数组
int[][] arrays = new int[res.size()][2];
for(int i=0;i<res.size();i++){
arrays[i][0] = res.get(i)[0];
arrays[i][1] = res.get(i)[1];
}
return arrays;
}

最后

以上就是自由人生为你收集整理的无序可重复数组中所有两个数相加等于一个固定数的下标组合的全部内容，希望文章能够帮你解决无序可重复数组中所有两个数相加等于一个固定数的下标组合所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。