algorithm - 查找具有给定总和的子数组

Question

我正在尝试实现查找具有给定总和的子数组的功能样式。我写的代码不符合功能风格。有人可以帮助使其更具功能性吗。

问题:给定一个未排序的非负整数数组，找到一个与给定数字相加的连续子数组。

输入:arr[] = {1, 4, 20, 3, 10, 5}，总和 = 33输出:在索引 2 和 4 之间找到的总和

输入:arr[] = {1, 4, 0, 0, 3, 10, 5}，总和 = 7输出:在索引 1 和 4 之间找到的总和

我可以用蛮力法解决这个问题。但正在寻找更有效的功能解决方案。

val sumList = list.foldLeft(List(0), 0)((l, r) => (l._1 :+ (l._2+r), l._2 + r))._1.drop(1)
  //Brute force approach
  sumList.zipWithIndex.combinations(2).toList.collectFirst({
    case i if i(1)._1 - i(0)._1 == sum => i
  }) match {
    case Some(List(x, y)) => println("elements which form the given sum are => "+ list.drop(x._2+1).take(y._2-x._2))
    case _ => println("couldn't find elements which satisfy the given condition")
  }

算法: 将变量 curr_sum 初始化为第一个元素。 curr_sum 表示当前子数组的和。从第二个元素开始，将所有元素一一添加到curr_sum。如果 curr_sum 变得等于 sum，则打印解决方案。如果 curr_sum 超过总和，则在 curr_sum 大于总和时删除尾随元素。

 val list:List[Int] = List(1, 4, 20, 3, 10, 5)
  val sum = 33
    
  val (totalSum, start, end, isSumFound) = list.zipWithIndex.drop(1).foldLeft(list.head, 0, 1, false)((l, r) =>
    if(!l._4) {
      val tempSum = l._1 + r._1
      if (tempSum == sum){
        (sum, l._2, r._2, true)
      } else if(tempSum > sum){
          var (curSum, curIndex) = (tempSum, l._2)
          while(curSum > sum && curIndex < list.length-1){
            curSum = curSum - list(curIndex)
            curIndex = l._2 +1
          }
        (curSum, curIndex, r._2, curSum == sum)
      } else {
        (tempSum, l._2, r._2, false)
      }
    }else
      l
  )

  if(isSumFound || totalSum == sum){
    println("elements which form the given sum are => "+ list.drop(start+1).take(end-start))
  }else{
    println("couldn't find elements which satisfy the given condition")
  }

Answer 1

val list:List[Int] = List(1, 4, 20, 3, 10, 5)
val sum = 33

一种返回子列表迭代器的方法，首先是从第一个元素开始的迭代器，然后从第二个元素开始...

def subLists[T](xs:List[T]):Iterator[List[T]] =
     if (xs == Nil) Iterator.empty
     else xs.inits ++ subLists(xs.tail)

找到第一个总和正确的列表

val ol = subLists(list).collectFirst{ case x if x.sum == sum => x}

然后再次查找索引，并打印结果

ol match {
    case None => println("No such subsequence")
    case Some(l) => val i = list.indexOfSlice(l)
                println("Sequence of sum " + sum +
                        " found between " + i +
                         " and " + (i + l.length - 1))
} 
//> Sequence of sum 33 found between 2 and 4

(您可以在构建迭代器时跟踪与子列表关联的索引，但这似乎比它的值(value)更麻烦，并且降低了 subLists 的一般用途)

编辑:这是您发布的更“实用”的代码版本。但我认为我的第一个版本更清晰——将生成序列的关注点与检查它们的总和分开更简单

 val sumList = list.scanLeft(0){_ + _}
 val is = for {i <- 1 to list.length - 1
                j <- 0 to i
                if sumList(i)-sumList(j) == sum}
             yield (j, i-1)

 is match {
    case Seq() => println("No such subsequence")
    case (start, end) +: _ =>
                 println("Sequence of sum " + sum +
                         " found between " + start + " and " + end )
 } 
 //> Sequence of sum 33 found between 2 and 4

EDIT2:这是一个 O(N) 的。 “功能性”，因为没有可变变量，但在我看来，它不如其他变量清晰。如果您只打印找到的结果会更清楚一点(不需要在迭代之间携带累加器的 rs 部分)但是这种副作用的方式似乎不太实用，所以我返回一个列表的解决方案。

 val sums = list.scanLeft(0)(_ + _) zipWithIndex
 sums.drop(1).foldLeft((sums, List[(Int, Int)]())) {
    case ((leftTotal, rs), total) =>
      val newL = leftTotal.dropWhile(total._1 - _._1 > target)
      if (total._1 - newL.head._1 == target)
        (newL, (newL.head._2, total._2 - 1) :: rs)
      else (newL, rs)
  }._2
  //> res0: List[(Int, Int)] = List((2,4))

O(N) 因为我们将缩短的 newL 作为下一次迭代传递给 leftTotal，所以 dropWhile 只会遍历列表一次。这个依赖于非负整数(因此添加另一个元素不能减少总数)，其他的也使用负整数。