描述:
给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标。
思路:
1、实现一个方法,将数组元素值和其对应的index存入HashMap(原因:HashMap的查找时间复杂度为O(1));
2、实现一个方法,输入一个数组、一个二手拍卖平台目标值,返回一个Map,Map中包含符合条件的元组
代码:
/**
* 将数组转换为HashMap,K-V 对应于 元素值-元素在数组中的index
*/
def transform(nums:Array[Int]):mutable.HashMap[Int,Int] ={ val hm = new mutable.HashMap[Int,Int]() if (nums.length ==0) hm else { for (n <- nums.indices){
hm.put(nums(n),n)
}
hm
}
} /**
* 两数之和,输入一个数组nums、一个目标数字target; 求存在于个nums中的两个数a和b,使得 a+b =target
* 返回值:map 其中K-V对应于 a,b在nums中的数组下标
*/
def twoSum(nums:Array[Int],target:Int) : mutable.HashMap[Int,Int] = { val resultMap = new mutable.HashMap[Int,Int]() val hm = transform(nums) //遍历数组,同时查找(target - nums(i))的值 是否出现在hm中,如果出现,则记录本次遍历结果中的i以及hm对应的index
for (i <- nums.indices) { if(hm.contains(target - nums(i) )){
resultMap.put(i,hm(target - nums(i)))
}
}
resultMap
} val nums = Array(10,3,24,6,0,9,6,43,34,2,21,20,25)
println(twoSum(nums,23))