请选择 进入手机版 | 继续访问电脑版

[IOS] IOS 算法 三数之和求解题目

[复制链接]
查看48 | 回复12 | 2021-9-13 17:19:28 | 显示全部楼层 |阅读模式
目次

IOS 算法三数之和求解题目

1、三数求和简单先容

对于一个整数的数组, 是否存在a, b, c 使得 a + b + c = 0, 返回a b c 数组,雷同 数组只返回一个,:

比方 :

  1. [-1, -2, 6, 5, 0, 1, 2, -1, -1] 返回 [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]]
复制代码

关键点:

  1. ① 找到和为0的三个数
  2. ② 去除相同项, 比如: 上面的数组 其实 [-1, 0, 1], 有三组, 但是我们只要添加1组
复制代码

万万 不要用

  1. for循环
复制代码
  1. 套一层for循环
复制代码
处理这个题目 , 有些以为 两层for循环求解, 可以啊, 一层探求 A, 2层探求 B, 判断 数组是否存在
  1. C = - (A + B),
复制代码
思绪 精确 , 但是这种时间复杂度很高
  1. O(n^2)
复制代码
而且上手时间 你会发现, 去重题目 处理起来比较繁琐

方法思绪 是:

数组

  1. nums 先正序排列
复制代码

然后

  1. for循环
复制代码
, 设置
  1. 最小值下标 low = i + 1
复制代码
,
  1. 最大值下标 high = nums.count - 1
复制代码

最大值, 最小值 不断紧缩 查找, 重复的去掉 且始终保持

  1. low < high
复制代码
(由于 是正序分列 大值 >= 小值)

使得 0 - nums = nums[low] + nums[high] (即: 0 = nums[low] + nums[high] + nums)

创建新数组 添加符合条件的 [nums[low], nums[high], nums], 循环竣事 返回即可

接下来我们看下代码

2、代码

  1. let num:[Int] = [0, 0, 0, 0, -1, 0, 1, 9, 7, 4]
  2. print("返回结果: \(self.caculate(nums: num))")
  3. func caculate(nums: [Int]) -> [[Int]] {
  4. //数组元素小于2直接返回
  5. if nums.count < 2 {
  6. return []
  7. }
  8. //创建空数组, 用来添加 [A,B,C]
  9. var result:[[Int]] = []
  10. //将原数组数组正序排列, 这一步很重要, 乱序数组很难处理
  11. let sort:[Int] = nums.sorted()
  12. //循环正序数组
  13. for i in 0..<sort.count-1 {
  14. //创建最小值下标, 最大值下标
  15. var low:Int = i+1
  16. var high:Int = sort.count - 1
  17. //A+B+C=0 定义-C 为了之后让 A+B=-C
  18. let target:Int = 0 - sort[i]
  19. //如果两个数相等直接跳过下一次循环
  20. if i>0 && sort[i] == sort[i-1] {
  21. continue
  22. }
  23. //始终保证 最大值下标 > 最小值下标
  24. //思路就是最大值不减小, 最小值不断增大, 最小值不会超过最大值
  25. //直到找到对应值, 相同值去重
  26. while low < high {
  27. //创建sum为: 两数字和 A+B
  28. let sum:Int = sort[low] + sort[high]
  29. //如果A+B == -C 即 A+B+C == 0
  30. if sum == target {
  31. //数组添加新元素
  32. result.append([sort[low], sort[high], sort[i]])
  33. //如果当前最小值和下一位相等, 下标往前移位, 去重
  34. while low < high && sort[low] == sort[low + 1] {
  35. low += 1
  36. }
  37. //如果当前最大值和前一位相等, 下标往前移位, 去重
  38. while low < high && sort[high] == sort[high - 1] {
  39. high -= 1
  40. }
  41. //最小值向后移动一位, 最大值向前移动一位 继续收缩, 直到跳出while
  42. low += 1
  43. high -= 1
  44. }else if sum < target{
  45. //如果A+B == -C 即 A+B+C == 0
  46. low += 1
  47. }else {
  48. //如果A+B == -C 即 A+B+C == 0
  49. high -= 1
  50. }
  51. }
  52. }
  53. return result
  54. }
复制代码

返回结果 :

  1. [[0, 1, -1], [0, 0, 0]]
复制代码

到此这篇关于IOS 算法之三数之和求解题目 的文章就先容 到这了,更多相干 IOS 算法三数之和求解内容请搜刮 脚本之家从前 的文章或继续欣赏 下面的相干 文章渴望 大家以后多多支持脚本之家!


免责声明:如果侵犯了您的权益,请联系站长,我们会及时删除侵权内容,谢谢合作!
回复

使用道具 举报

avatar 木易549 | 2021-9-19 16:53:05 | 显示全部楼层
这一年啥事没干,光研究admin楼主的帖子了!
回复

使用道具 举报

avatar 木头哈喇子崭 | 2021-9-20 01:23:26 | 显示全部楼层
我就搞不明白了,看帖回帖能死人么,居然只有我这么认真的在回帖!
回复

使用道具 举报

avatar 默默MYQ | 2021-10-6 16:58:57 | 显示全部楼层
小弟默默的路过贵宝地~~~
回复

使用道具 举报

avatar 123457305 | 2021-10-7 14:03:45 | 显示全部楼层
没人理我,好伤心啊!
回复

使用道具 举报

avatar 潘多拉945 | 2021-10-9 05:17:31 | 显示全部楼层
今天的心情很不错啊
回复

使用道具 举报

avatar 我的苦恼冉 | 2021-10-9 10:25:16 | 显示全部楼层
好好学习admin楼主的帖子!
回复

使用道具 举报

avatar 钟情695 | 2021-10-9 10:25:21 | 显示全部楼层
admin楼主,我告诉你一个你不知道的的秘密,有一个牛逼的网站,他卖的服务器是永久的,我们的网站用 服务器都是在这家买的,你可以去试试。访问地址:http://fwq.mxswl.com
回复

使用道具 举报

楼上的说的很好!
回复

使用道具 举报

avatar ai2017 | 3 天前 | 显示全部楼层
admin楼主主机很热情啊!
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则