AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2022-08-22 259
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： ​LeetCode 里分别有两数之和，三数之和，四数之和，主要实现方法为 Python，Java，C++，下面使用 scala 分别实现。

一.引言

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

二.两数之和

1.题目要求

image.gif编辑

给定数组 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
  }

image.gif

C.执行效率

image.gif编辑

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

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
  }

image.gif

C.执行效率

image.gif编辑

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

4.HashMap 简化版

A.优化分析

image.gif编辑

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

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

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

· 同时判断 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
  }

image.gif

C.执行效率

image.gif编辑

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
  }

image.gif

C.执行效率

image.gif编辑

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

三.三数之和

1.题目要求

image.gif编辑

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

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
    }
}

image.gif

C.执行效率

image.gif编辑

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

四.四数之和

1.题目要求

image.gif编辑

除了三数之和，官方居然还给了一道四数之和，这次又从数值变为了返回索引，且要求 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
  }

image.gif

C.执行效率

image.gif编辑

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

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

image.gif

结果是 -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
    }
}

image.gif

这次完美通过了~

image.gif编辑

五.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。

文章标签：
Java
C++
Python
索引
Scala
算法
存储
关键词：
LeetCode scala
BIT_666
目录
相关文章
BIT_666
|
算法 Scala 索引
LeetCode / Scala - 无重复字符最长子串 ，最长回文子串
​ LeetCode 里有一类字符子串问题，这里主要分析无重复字符的最长子串与最长回文子串，总结相关方法。
BIT_666
115 0
LeetCode / Scala - 无重复字符最长子串 ，最长回文子串
BetterBench
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - III. 从上到下打印二叉树 III
本文介绍了两种Python实现方法，用于按照之字形顺序打印二叉树的层次遍历结果，实现了在奇数层正序、偶数层反序打印节点的功能。
BetterBench
27 6
BetterBench
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 26. 树的子结构
这篇文章提供了解决LeetCode上"剑指Offer 26. 树的子结构"问题的Python代码实现和解析，判断一棵树B是否是另一棵树A的子结构。
BetterBench
28 4
BetterBench
|
13天前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法，提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法，并给出了Python实现代码。
BetterBench
42 2
BetterBench
|
13天前
|
索引 Python
【Leetcode刷题Python】从列表list中创建一颗二叉树
本文介绍了如何使用Python递归函数从列表中创建二叉树，其中每个节点的左右子节点索引分别是当前节点索引的2倍加1和2倍加2。
BetterBench
16 7
BetterBench
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 30. 包含min函数的栈
本文提供了实现一个包含min函数的栈的Python代码，确保min、push和pop操作的时间复杂度为O(1)。
BetterBench
13 4
BetterBench
|
14天前
|
Python
【Leetcode刷题Python】剑指 Offer 22. 链表中倒数第k个节点
Leetcode题目"剑指 Offer 22. 链表中倒数第k个节点"的Python解决方案，使用双指针法找到并返回链表中倒数第k个节点。
BetterBench
32 5
BetterBench
|
13天前
|
算法 Python
【Leetcode刷题Python】 LeetCode 2038. 如果相邻两个颜色均相同则删除当前颜色
本文介绍了LeetCode 2038题的解法，题目要求在一个由'A'和'B'组成的字符串中，按照特定规则轮流删除颜色片段，判断Alice是否能够获胜，并提供了Python的实现代码。
BetterBench
25 3
BetterBench
|
13天前
|
算法 Python
【Leetcode刷题Python】剑指 Offer 33. 二叉搜索树的后序遍历序列
本文提供了一种Python算法，用以判断给定整数数组是否为某二叉搜索树的后序遍历结果，通过识别根节点并递归验证左右子树的值是否满足二叉搜索树的性质。
BetterBench
11 3
BetterBench
|
13天前
|
Python
【Leetcode刷题Python】剑指 Offer 32 - II. 从上到下打印二叉树 II
本文提供了一种Python实现方法，用于层次遍历二叉树并按层打印结果，每层节点按从左到右的顺序排列，每层打印到一行。
BetterBench
24 3