一.引言
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。