个人中心
gpt4 book ai didi

IOS 算法 三数之和求解问题

转载 作者：qq735679552 更新时间：2022-09-27 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章IOS 算法 三数之和求解问题由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

IOS 算法三数之和求解问题

1、三数求和简单介绍

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

例如

[-1, -2, 6, 5, 0, 1, 2, -1, -1] 返回 [[-1, 0, 1], [-2, 0, 2], [-1, -1, 2]] 。

关键点:

① 找到和为0的三个数 。

② 去除相同项, 比如: 上面的数组 其实 [-1, 0, 1], 有三组, 但是我们只要添加1组 。

千万不要用 for循环又套一层for循环 处理这个问题, 有些认为两层for循环求解, 可以啊, 一层寻找A, 2层寻找B, 判断数组是否存在C = - (A + B), 思路正确, 但是这种时间复杂度很高O(n^2) 而且上手时候你会发现, 去重问题处理起来比较繁琐 。

方法思路是:

数组nums 先正序排列 。

然后for循环, 设置最小值下标 low = i + 1, 最大值下标 high = nums.count - 1 。

最大值, 最小值 不断收缩查找, 重复的去掉 且始终保持 low < high (因为是正序排列 大值 >= 小值) 。

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

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

接下来我们看下代码 。

2、代码

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

返回结果: [[0, 1, -1], [0, 0, 0]] 。

到此这篇关于IOS 算法之三数之和求解问题的文章就介绍到这了,更多相关IOS 算法三数之和求解内容请搜索我以前的文章或继续浏览下面的相关文章希望大家以后多多支持我！ 。

原文链接：https://www.jianshu.com/p/e909ebb9c80b 。

最后此篇关于IOS 算法 三数之和求解问题的文章就讲到这里了,如果你想了解更多关于IOS 算法 三数之和求解问题的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： iOS文本的多语言适配以及实践指南
文章推荐： iOS masonry的使用方法
文章推荐： IOS NSTimeInterval使用案例详解
文章推荐： R语言基本画图函数与多图多线的用法
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com