服务器之家:专注于服务器技术及软件下载分享
分类导航

PHP教程|ASP.NET教程|Java教程|ASP教程|编程技术|正则表达式|C/C++|IOS|C#|Swift|Android|VB|R语言|JavaScript|易语言|vb.net|

服务器之家 - 编程语言 - IOS - IOS 算法 三数之和求解问题

IOS 算法 三数之和求解问题

2021-12-28 17:19ShawnAlex IOS

这篇文章主要介绍了IOS 算法 三数之和求解问题,属于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

延伸 · 阅读

精彩推荐
  • IOSiOS中tableview 两级cell的展开与收回的示例代码

    iOS中tableview 两级cell的展开与收回的示例代码

    本篇文章主要介绍了iOS中tableview 两级cell的展开与收回的示例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧...

    J_Kang3862021-04-22
  • IOSiOS通过逆向理解Block的内存模型

    iOS通过逆向理解Block的内存模型

    自从对 iOS 的逆向初窥门径后,我也经常通过它来分析一些比较大的应用,参考一下这些应用中某些功能的实现。这个探索的过程乐趣多多,不仅能满足自...

    Swiftyper12832021-03-03
  • IOSIOS 屏幕适配方案实现缩放window的示例代码

    IOS 屏幕适配方案实现缩放window的示例代码

    这篇文章主要介绍了IOS 屏幕适配方案实现缩放window的示例代码,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要...

    xiari5772021-06-01
  • IOS关于iOS自适应cell行高的那些事儿

    关于iOS自适应cell行高的那些事儿

    这篇文章主要给大家介绍了关于iOS自适应cell行高的那些事儿,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的...

    daisy6092021-05-17
  • IOS解析iOS开发中的FirstResponder第一响应对象

    解析iOS开发中的FirstResponder第一响应对象

    这篇文章主要介绍了解析iOS开发中的FirstResponder第一响应对象,包括View的FirstResponder的释放问题,需要的朋友可以参考下...

    一片枫叶4662020-12-25
  • IOSIOS开发之字典转字符串的实例详解

    IOS开发之字典转字符串的实例详解

    这篇文章主要介绍了IOS开发之字典转字符串的实例详解的相关资料,希望通过本文能帮助到大家,让大家掌握这样的方法,需要的朋友可以参考下...

    苦练内功5832021-04-01
  • IOSiOS 雷达效果实例详解

    iOS 雷达效果实例详解

    这篇文章主要介绍了iOS 雷达效果实例详解的相关资料,需要的朋友可以参考下...

    SimpleWorld11022021-01-28
  • IOSiOS布局渲染之UIView方法的调用时机详解

    iOS布局渲染之UIView方法的调用时机详解

    在你刚开始开发 iOS 应用时,最难避免或者是调试的就是和布局相关的问题,下面这篇文章主要给大家介绍了关于iOS布局渲染之UIView方法调用时机的相关资料...

    windtersharp7642021-05-04