LeetCode / Scala - 两数，三数，四数，N数之和-阿里云开发者社区

一.引言

LeetCode 里分别有两数之和，三数之和，四数之和，主要实现方法为 Python，Java，C++，下面使用 scala 分别实现，并推导 N 数之和实现方法。

二.两数之和

1.题目要求

编辑

给定数组 nums 和 target，返回下标 i、j 满足 nums[i] + nums[j] = target，这里注意只会存在一个有效答案。

2.暴力循环版

A.思路分析

直接起两个 For 循环，分别遍历 nums 数组的元素，如果满足 nums[i] + nums[j] = target 且 i != j，则说明找到结果。

B.代码实现

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    nums.indices.foreach(i => { // 遍历数组每一个元素
      nums.indices.foreach(j => { // 遍历数组每一个元素
        if (nums(i) + nums(j) == target && i != j) { // 去重
          return Array(i, j)
        }
      })
    })
    null
  }

C.执行效率

编辑

通过最朴素的方法通过所有示例，但是执行用时感人。

3. HashMap 清晰版

A.思路分析

可以通过 HashMap 存储 nums 中数字的索引，只需遍历一次 nums 数组，如果 num 和 target - num 都在 HashMap 的 key 中，则返回 num 和 target - num 对应的索引 index。

Tips:

scala 可以通过 zipWithIndex 实现 nums 数组与索引 index 的对应，最早我直接使用 toMap，但是有一个问题，即如果 nums 存在相同 num 时会造成 index 覆盖从而丢失，所以有了下面排除两数相等的特殊情况。

B.代码实现

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val result = new Array[Int](2) // 存储结果
    val indexMap = new mutable.HashMap[Int, Int]() // 存储映射关系
    // 存储数字与索引
    nums.zipWithIndex.foreach(kv => {
      if (!indexMap.contains(kv._1)) {
        indexMap(kv._1) = kv._2
      } else {
        if (kv._1 * 2 == target) { // 排除两数相等的特殊情况
          result(0) = indexMap(kv._1)
          result(1) = kv._2
          return result
        }
      }
    })
    // 通过判断 num 与 target - num 是否都存在与 indexMap
    nums.foreach(num => {
      val otherNum = target - num
      if (indexMap.contains(otherNum) && num != otherNum) {
        result(0) = indexMap(num)
        result(1) = indexMap(otherNum)
        return result
      }
    })
    result
  }

C.执行效率

编辑

使用 HashMap 代替 For 循环空间换时间，内存占用过大，运行速度偏慢。

4.HashMap 简化版

A.优化分析

编辑

会看一下上述代码，这里把优化点整理一下：

· 结果只有一个，不需要提前初始化，节省内存

· 无需单独存储，可以边存储边判断，节省时间空间

· 同时判断 num 与 target - num 缩短时间

时间复杂度 O(N)-遍历 nums 数组，空间复杂度 O(N) - 存储HashMap

B.代码实现

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    val indexMap = new mutable.HashMap[Int, Int]()
    var index = 0 // 累加索引
    nums.foreach(num => {
      // 判断 target - num 是否也存在与 map
      val flag: Int = indexMap.getOrElse(target - num, -1)
      if (flag != -1) {
        return Array(index, flag)
      }
      indexMap(num) = index // 保存映射
      index += 1
    })
    null
  }

C.执行效率

编辑

5.双指针版

A.思路分析

首先将数组排序得到有序数组，然后指针索引 left = 0 与 rigth = nums.length - 1，判断 sum = nums[left] + nums[right] 与 target 的大小，如果 sum > target 则将 right - 1，如果 sum < target 则 left + 1，相等则通过 Array.indexOf 获取对应元素的索引 index。

B.代码实现

def twoSum(nums: Array[Int], target: Int): Array[Int] = {
    // 数组排序
    val sortedNums = nums.sorted
    // 判断重复情况
    val mid = target / 2
    if (nums.contains(mid)) {
      val re = nums.zipWithIndex.filter(_._1.equals(mid)).map(_._2)
      if (re.length > 1) {
        return re
      }
    }
    // 双指针遍历
    var left = 0
    var right = sortedNums.length - 1
    while (left < right) {
      val sum = sortedNums(left) + sortedNums(right)
      if (sum == target) {
        // indexOf 获取元素索引
        return Array(nums.indexOf(sortedNums(left)), nums.indexOf(sortedNums(right)))
      } else if (sum > target) {
        right -= 1
      } else {
        left += 1
      }
    }
    null
  }

C.执行效率

编辑

由于需要考虑去重的情况所以拖慢了执行时间。这里主要引入了双指针的思想，后续三数之和，四数之和都需要双指针来解决。

三.三数之和

1.题目要求

编辑

与两数之和基本类似，差别在于本例返回数字即可而不是下标，其次这里答案可能不唯一。

2.双指针版

A.思路分析

最无脑的肯定还是三个 For 循环，然后判断 a + b + c = 0，这里就不写了，直接说一下三指针的思路：

-> 将数组排序得到有序数组

-> 固定第一个位置的元素为 start，如果该位置元素大于0则退出循环，因为数组有序且要求和为0

-> 规定 left = start + 1，right = nums.length - 1，sum = nums(start) + nums(left) + nums(right)

sum > 0，太大了，right - 1

sum < 0，太小了，left + 1

sum = 0，将 nums(start) 、nums(left) 、nums(right) 三个数字添加至候选集

Tips:

由于上述题目要求不能出现重复解，所以注意判断 start 和 start - 1 的元素是否相同，然后分析算法复杂度，时间复杂度 O(n^2)，数组排序 O(N*logN)，遍历数组、双指针 O(N)，空间复杂度 O(1)

B.实现代码

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks.{break, breakable}
object Solution {
    def threeSum(nums: Array[Int]): List[List[Int]] = {
    // 异常判断
    val length = nums.length
    if (length < 3 || nums.isEmpty) {
      return null
    }
    val sortedNums = nums.sorted // 数组排序
    val result = new ArrayBuffer[List[Int]]()
    sortedNums.indices.foreach(index => {
      breakable {
        // 当前数字大于0，则后面数字相加不可能为0
        if (sortedNums(index) > 0) {
          return result.toList
        }
        // 排除异常值
        if (index > 0 && sortedNums(index) == sortedNums(index - 1)) break()
        var left = index + 1
        var right = length - 1
        while (left < right) {
          val sumValue = sortedNums(index) + sortedNums(left) + sortedNums(right)
          // 排除重复值
          if (index > 0 && sortedNums(index) == sortedNums(index - 1)) {
            left = index + 1
            right = length - 1
            break()
          }
          if (sumValue.equals(0)) {
            result.append(Array(sortedNums(index), sortedNums(left), sortedNums(right)).toList)
            while (left < right && sortedNums(left) == sortedNums(left + 1)) {
              left += 1
            }
            while (left < right && sortedNums(right) == sortedNums(right - 1)) {
              right -= 1
            }
            left += 1
            right -= 1
          } else if (sumValue > 0) {
            right -= 1
          } else {
            left += 1
          }
        }
      }
    })
    result.toList
    }
}

C.执行效率

编辑

由于 scala 默认不支持 break 和 continue，所以需要手工引入 scala.util.control.Breaks.{break, breakable} 两个类辅助实现 break 和 continue 的方法。

四.四数之和

1.题目要求

编辑

除了三数之和，官方居然还给了一道四数之和，这次又从数值变为了返回索引，且要求 a、b、c、d 各不相同。

2.双指针 👍

A.思路分析

三数相加采用固定第一个位置 start，然后双指针遍历的方法，这里拓展为固定前两个位置 i，j，首先将数组排序实现有序，需要满足 j > i，然后 left = j + 1，right = nums.length - 1，随后判断 sum = nums(i) + nums(j) + nums(left) + nums(right) 与 target 的关系，太大 right -1 ，太小 left + 1，逐级判断，循环一次后再累加 i or j，继续循环。

Tips：

时间复杂度: 数组排序 O(NLogN)，遍历第一位 O(N)，遍历第二位 O(N)，双指针 O(N) 整体 O(N^3)

B.代码实现

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks.{break, breakable}
object FourNum_18 {
  def fourSumV1(nums: Array[Int], target: Int): List[List[Int]] = {
    val result = new ArrayBuffer[List[Int]]()
    // 数组合法性
    if (nums == null) {
      return result.toList
    }
    // 长度合法性
    val length = nums.length
    if (length < 4) {
      return result.toList
    }
    // 数组排序
    val sortedNums = nums.sorted
    breakable {
      (0 to length - 4).filter(first => { // 使用 filter 代替 continue
        !(first > 0 && sortedNums(first) == sortedNums(first - 1)) &&
        !(sortedNums(first) + sortedNums(length - 3) + sortedNums(length - 2) + sortedNums(length - 1) < target)
      }).foreach(first => {
        // 最小的四个数超过 target
        if (sortedNums(first) + sortedNums(first + 1) + sortedNums(first + 2) + sortedNums(first + 3) > target) {
          break()
        }
        breakable {
          (first + 1 to length - 3).filter(second => { // 使用 filter 代替 continue
            !(second > first + 1 && sortedNums(second) == sortedNums(second - 1)) &&
              !(sortedNums(first) + sortedNums(second) + sortedNums(length - 2) + sortedNums(length - 1) < target)
          }).foreach(second => {
            if (sortedNums(first) + sortedNums(second) + sortedNums(second + 1) + sortedNums(second + 2) > target) {
              break()
            }
            var left = second + 1
            var right = length - 1
            while (left < right) { // 判断 sum 与 target 的关系
              val sum: Long = sortedNums(first) + sortedNums(second) + sortedNums(left) + sortedNums(right)
              if (sum.equals(target.toLong)) {
                result.append(Array(sortedNums(first), sortedNums(second), sortedNums(left), sortedNums(right)).toList)
                while (left < right && sortedNums(left) == sortedNums(left + 1)) {
                  left += 1
                }
                left += 1
                while (left < right && sortedNums(right) == sortedNums(right - 1)) {
                  right -= 1
                }
                right -= 1
              } else if (sum < target) {
                left += 1
              } else {
                right -= 1
              }
            }
          })
        }
      })
    }
    result.toList
  }

C.执行效率

编辑

BBQ 了，最后几个示例翻车了，拿测试的 nums 和 target 在本地试一下：

val int: Int = 1000000000 + 1000000000 + 1000000000
   println(int)

结果是 -1294967296，Int 最大值为 2147483647，这里三个 1000000000 相加超过了 Int 范围从而导致 sum 结果异常，从而影响 sum 与 target 的判断。

D.修复

scala 中如果 Long + Int 会得到 Long，基于上述越界的问题，我们在 sum 时将 nums(start) 转换为 Long，再将 target 转换为 Long，此时不会出现数组越界问题：

import scala.collection.mutable.ArrayBuffer
import scala.util.control.Breaks.{break, breakable}
object Solution {
    def fourSum(nums: Array[Int], target: Int): List[List[Int]] = {
    val result = new ArrayBuffer[List[Int]]()
    if (nums == null) {
      return result.toList
    }
    val length = nums.length
    if (length < 4) {
      return result.toList
    }
    val sortedNums = nums.sorted
    breakable {
      (0 to length - 4).filter(first => {
        !(first > 0 && sortedNums(first) == sortedNums(first - 1)) &&
          !(sortedNums(first).toLong + sortedNums(length - 3) + sortedNums(length - 2) + sortedNums(length - 1) < target.toLong)
      }).foreach(first => {
        // 最小的四个数超过 target
        if (sortedNums(first).toLong + sortedNums(first + 1) + sortedNums(first + 2) + sortedNums(first + 3) > target.toLong) {
          break()
        }
        breakable {
          (first + 1 to length - 3).filter(second => {
            !(second > first + 1 && sortedNums(second) == sortedNums(second - 1)) &&
              !(sortedNums(first).toLong + sortedNums(second) + sortedNums(length - 2) + sortedNums(length - 1) < target.toLong)
          }).foreach(second => {
            if (sortedNums(first).toLong + sortedNums(second) + sortedNums(second + 1) + sortedNums(second + 2) > target.toLong) {
              break()
            }
            var left = second + 1
            var right = length - 1
            while (left < right) {
              // 第一位 toLong target toLong
              val sum = sortedNums(first).toLong + sortedNums(second) + sortedNums(left) + sortedNums(right)
              if (sum.equals(target.toLong)) {
                result.append(Array(sortedNums(first), sortedNums(second), sortedNums(left), sortedNums(right)).toList)
                while (left < right && sortedNums(left) == sortedNums(left + 1)) {
                  left += 1
                }
                left += 1
                while (left < right && sortedNums(right) == sortedNums(right - 1)) {
                  right -= 1
                }
                right -= 1
              } else if (sum < target.toLong) {
                left += 1
              } else {
                right -= 1
              }
            }
          })
        }
      })
    }
    result.toList
    }
}

这次完美通过了~

编辑

五.N数之和

前面提到了两数、三数、四数之和，这里可以根据数学的数学归纳法进行 N 数之和的推理。

1.证明

首先将数组排序

K = 1 时，一数之和，这个直接遍历判断即可，没有问题

K = N 时，固定前 N-2 位，对最后两位执行双指针，上面已实现并验证无误

当 K = N+1 时，针对 nums 中的每个数字 num 及其索引 index，将 K=N+1 转换为 K= N 的问题:

nums(1) + nums(2) + ... + nums(index) + ... + nums(N+1) = target (K=N+1)

转换为 ↓

nums(1) + nums(2) + ... + nums(N+1) = target - nums(index) (K=N)

只需将转换后 N+1 个 K=N 的问题答案汇总到一个 List 中，即为 K=N+1 时的解决方案，证毕。

2.总结表述

当 K=N 时，固定前 N-2 位，最后两位采用双指针遍历，可以解决 Target 问题。

六.总结

随着 N 的增大，除了循环的时间复杂度增加外，也需要考虑更多的剪枝条件，例如 target=0 时 start 元素已大于 0 、前几个元素 sum 已超 target 等，这些条件过滤掉可以提升运行速度。除此之外，Scala 默认不支持 continue 与 break 方法，所以 python、java 很多步骤可以直接 continue 轻松跳过，而 scala 需要注意 breakable 所包围的函数体和何时何地 break，相对来说需要对逻辑把控更清晰，有需要的同学可以参考：Scala/Java - break & continue。

LeetCode / Scala - 两数，三数，四数，N数之和

一.引言

二.两数之和

1.题目要求

2.暴力循环版

3. HashMap 清晰版

4.HashMap 简化版

5.双指针版

三.三数之和

1.题目要求

2.双指针版

四.四数之和

1.题目要求

2.双指针 👍

五.N数之和

1.证明

2.总结表述

六.总结

热门文章

最新文章

相关课程

相关电子书

热门

活动广场

任务中心

开发者评测

高校计划

乘风者计划

训练营

阿里云MVP

话题

直播

下载

镜像站

技术资料

插件

LeetCode / Scala - 两数，三数，四数，N数之和

一.引言

二.两数之和

1.题目要求

2.暴力循环版

3. HashMap 清晰版

4.HashMap 简化版

5.双指针版

三.三数之和

1.题目要求

2.双指针版

四.四数之和

1.题目要求

2.双指针 👍

五.N数之和

1.证明

2.总结表述

六.总结

热门文章

最新文章

相关课程

相关电子书