手记

Scala 两数之和

描述:

    给定一个整数数组 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))


0人推荐
随时随地看视频
慕课网APP