IOS 算法 三数之和求解问题_IOS

来源:脚本之家  责任编辑:小易  
目录
IOS 算法三数之和求解问题1、三数求和简单介绍2、代码

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、代码

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 算法三数之和求解内容请搜索真格学网以前的文章或继续浏览下面的相关文章希望大家以后多多支持真格学网!

您可能感兴趣的文章:iOS常见算法以及应用知识点总结iOS常用算法之两个有序数组合并(要求时间复杂度为0(n))iOS中排列组合算法的使用小结iOS实现高效裁剪图片圆角算法教程iOS算法教程之分段截取常数示例ios使用OC写算法之递归实现八皇后iOS中MD5加密算法的介绍和使用IOS面试大全之常见算法iOS常用加密算法介绍和代码实践

  • 本文相关:
  • ios实现日历翻页动画
  • ios指纹识别的简单应用
  • ios实现高效裁剪图片圆角算法教程
  • ios textfiled与textview 键盘的收起以及处理键盘遮挡
  • ios wkwebview适配实战篇
  • ios crash常规跟踪方法及bugly集成运用详细介绍
  • ios 9无法访问http的解决方法
  • ios开发中使用writetofile时的注意事项
  • ios添加购物车动画效果示例
  • ios导航栏对控制器view的影响详解
  • 甲、乙、丙三数之和是140,甲数除以乙数,丙数除以甲数,商都是...
  • 请问:三数之和是120甲数是乙数的2倍,丙比乙多20,三个数各是...
  • 甲、乙、丙三数之和是200,已知甲是乙的3倍,丙又是甲的2倍,求...
  • 问一道数学问题,甲.乙.丙三数之和为183,乙比丙的2倍少4,甲比...
  • 被减数、减数、差三数之和为80,求被减数.求高手解答。
  • 数学问题(高分!!!)1、甲乙丙三数之和是200.甲为乙的3倍,丙为甲...
  • 甲乙丙三数之和是183,甲数比乙数的2倍多7,丙数比乙数的3倍少...
  • 网站首页网页制作脚本下载服务器操作系统网站运营平面设计媒体动画电脑基础硬件教程网络安全c#教程vbvb.netc 语言java编程delphijavaandroidiosswiftscala易语言汇编语言r语言其它相关首页iosios常见算法以及应用知识点总结ios常用算法之两个有序数组合并(要求时间复杂度为0(n))ios中排列组合算法的使用小结ios实现高效裁剪图片圆角算法教程ios算法教程之分段截取常数示例ios使用oc写算法之递归实现八皇后ios中md5加密算法的介绍和使用ios面试大全之常见算法ios常用加密算法介绍和代码实践ios实现日历翻页动画ios指纹识别的简单应用ios实现高效裁剪图片圆角算法教程ios textfiled与textview 键盘的收起以及处理键盘遮挡ios wkwebview适配实战篇ios crash常规跟踪方法及bugly集成运用详细介绍ios 9无法访问http的解决方法ios开发中使用writetofile时的注意事项ios添加购物车动画效果示例ios导航栏对控制器view的影响详解objective-c中字符串的拼接方法小xcode使用教程详细讲解(全)ios开发中viewcontroller的页面跳ios毛玻璃效果的实现及图片模糊效ios为uiview设置阴影效果ios设置uibutton文字显示位置和字ios内存错误exc_bad_access的解决ios 签名错误codesign failed wiios获取各种文件目录路径的方法详解ios中button按钮的状态和点击ios 隐藏导航条和状态栏实现方法ios读写json文件的方法示例ios百度地图的使用(普通定位、反地理编码ios观察者设计模式iphone x官方文档的适配学习详解ios中判断emoji表情问题ios体验性优化之rtl适配右滑返回的实现ios app重提提交审核流程分享一个ios下实现基本绘画板功能的简单方ios实现双向滑动条效果
    免责声明 - 关于我们 - 联系我们 - 广告联系 - 友情链接 - 帮助中心 - 频道导航
    Copyright © 2017 www.zgxue.com All Rights Reserved