三数之和以及拓展

leetcode: 15

思路有两个：

1. 简化成two_sum ， 见way1, 但是运行时间过程没通过
2. 固定第一个，然后双指针跑剩下两个sum，关键点是：先排序，且跳过相同元素，以保证不重复， 优化速度的方式是：第二层和第三层的双指针是反向跑的。

另外一个优化的是，第三层的快速 -- , 没有这个优化或者用其他的优化方式（比如跳过第三层相同的元素），scala的代码过不了

todo：

1. Done 改成递归，递归可以完成 n-sum
   需要的： 剩余的n， 剩余的target-sum， 思路：n-sum(list, n, left-target-sum) = n-sum(list.tail, n - 1, left-target-sum - list.head) ++ n-sum(list.tail, n, left-target-sum)
2. 可以用二分查找，对于第三层，可以用二分查找

object Solution {
    def threeSum(nums: Array[Int]): List[List[Int]] = {
        // brute not good
        // threeSum_way1(nums)
        // double pointer
        // 我发现了，只是scala单纯的慢而已！！！！
        threeSum_way2(nums)
    }



  private def quickSort(nums: Array[Int]): Array[Int] = {
    import scala.collection.mutable
    /**
     * @param ns
     * @param start idx of first [...
     * @param end idx of last ...]
     */
    def partition(ns:mutable.ArraySeq[Int], start: Int, end: Int): Int = {
      if(start >= end) {
        start
      } else {
        var i = start
        var j = end
        val p = ns(start)
        // when enter this loop
        // i becaome the idx of last unused idx of smaller value
        while (i < j) {
          while( i < j && ns(j) >= p) { // ensure safe
            j -= 1
          }
          ns(i) = ns(j)
          // j become the idx of last unused idx of bigger value
          while(i < j && ns(i) <= p) {
            i += 1
          }
          ns(j) = ns(i)
        }
        ns(i) = p
        i
      }
    }

    def sort(ns: mutable.ArraySeq[Int], start:Int, end:Int): Unit = {
      if( start >= end) {
        ()
      }else {
        val part = partition(ns, start, end)
        sort(ns, start, part - 1)
        sort(ns, part + 1, end)
      }
    }
    val ans: mutable.ArraySeq[Int] = mutable.ArraySeq(nums:_*)
    sort(ans, 0, nums.length - 1)
    ans.toArray
  }

  def threeSum_way2(nums: Array[Int]): List[List[Int]] = {
    val ns: Array[Int] = nums.sorted
    val n = 3
    val target = 0
    // way1 for-loop
    // way2 iter

    //way1
    def forLoop(): List[List[Int]] = {
      import scala.collection.mutable
      val anss = mutable.ListBuffer[List[Int]]()
      var i = 0
      var j = 0
      var k = 0
      while (i < ns.length) {
        if (i == 0 || ns(i) != ns(i - 1)) {
          j = i + 1
          val sum = target - ns(i)
          while (j < ns.length) {
            if (j == i + 1 || ns(j) != ns(j - 1)) {
              k = ns.length - 1
              while (k > j && ((ns(j) + ns(k) > sum))) {
                k -= 1
              }
              if (k != j && ns(j) + ns(k) == sum) {
                anss.append(List(ns(i), ns(j), ns(k)))
              }
              k = j // go out
            }
            j += 1
          }
        }
        i += 1
      }
      anss.toList
    }


    forLoop()
  }


  def threeSum_way1(nums: Array[Int]): List[List[Int]] = {
    import scala.collection.mutable
    // 对于每个索引上的值，是否有其他两个之和为它的负数
    val target = 0
    // 转化成two-sum的问题
    def twoSum(nums: Array[Int], excludeIdx:Int, newSum: Int): List[List[Int]] = {
      val ans = mutable.ListBuffer[List[Int]]()
      val occured = mutable.Map[Int,List[Int]]()
      for {
        idx <- nums.indices
        if(idx != excludeIdx)
      } {
        if(occured.contains(nums(idx))) {
          val as = occured(nums(idx))
          as.foreach(a1 => ans.append(List(a1,idx)))
        } else {
          occured.put(newSum - nums(idx), occured.getOrElse(newSum - nums(idx), List.empty[Int]).+:(idx))
        }
      }
      ans.toList
    }

    val anss: Set[List[Int]] = nums.indices.map(idx => twoSum(nums, idx, target - nums(idx))).zipWithIndex.flatMap {
      case (ls, idx) => ls.map(_.+:(idx).map(nums).sorted)
    }.toSet
    anss.toList
  }
}

n-sum

val list = List(1,0,-1,0,-2,2)


def nSum(li:List[Int], pos:Int, idxs: List[Int], n: Int, leftedSum: Int): List[List[Int]] = {
  if(n == 0 && leftedSum == 0) {
    List(idxs.map(li))
  }else{
    if(li.length - pos < n || pos >= li.length) {
      List.empty[List[Int]]
    }else {
      println(pos)
     val ans1 =  nSum(li, pos + 1, idxs :+ pos, n - 1, leftedSum - li(pos))
     val ans2 = nSum(li, pos + 1, idxs, n, leftedSum)
    ans1 ++ ans2
    }
  }
}

val ans = nSum(list, 0, List.empty[Int], 4, 0)