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

时间: 2021-08-31

iOS常见算法以及应用知识点总结

算法比较 关键词 二分 递归 分治 回溯 冒泡排序 思想:两次循环,外层进行循环次数的控制,内层循环,进行数据之间的比较,大的数据上浮(下沉) #pragma mark - Objective-C //冒泡排序 - (void)bubbleSort:(id)array{ if (!([array isKindOfClass:[NSArray class]] || [array isKindOfClass:[NSMutableArray class]])) { NSLog(@"传入的参数不是数组类

ios使用OC写算法之递归实现八皇后

八皇后算法介绍 知道国际象棋的朋友们应该知道里面的皇后是最厉害的角色,她可以上下左右通吃,和中国象棋里面的车(ju 一声)一样,但是她比车更强大,她可以在斜线上也做到通吃,而我们的八皇后问题其实简单来说就是如何能够在 8×8 的国际象棋棋盘上放置八个皇后,使得任何一个皇后都无法直接吃掉其他的皇后 八皇后算法思路解析 既然任意一个皇后都无法吃掉其他的皇后,也就是说任两个皇后都不能处于同一条横行.纵行或斜线上,我们将棋盘当做一个二维数组,将皇后的位置标记为1 而其他位置默认都为0,这样我们就可以使用

iOS算法教程之分段截取常数示例

前言 本文主要给大家介绍了关于iOS算法之分段截取常数的相关内容,分享出来供大家参考学习价值,下面话不多说了,来一起看看详细的介绍吧. 一.错位分段相加,递归合并的过程 #include intHamming_weight_3(intn ) { n = (n&0x55555555) + ((n>>1)&0x55555555); n = (n&0x33333333) + ((n>>2)&0x33333333); n = (n&0x0f0f0f0

iOS常用加密算法介绍和代码实践

iOS系统库中定义了软件开发中常用的加解密算法,接口为C语言形式.具体包括了以下几个大类: #include <CommonCrypto/CommonCryptor.h> //常用加解密算法 #include <CommonCrypto/CommonDigest.h> //摘要算法 #include <CommonCrypto/CommonHMAC.h> #include <CommonCrypto/CommonKeyDerivation.h> #inclu

iOS常用算法之两个有序数组合并(要求时间复杂度为0(n))

思路: 常规思路: 先将一个数组作为合并后的数组, 然后遍历第二个数组的每项元素, 一一对比, 直到找到合适的, 就插入进去; 简单思路: 设置数组C, 对比A和B数组的首项元素, 找到最小的, 就放入数组C,依次进行下去. 代码如下: - (NSArray *)mergeOrderArrayWithFirstArray: (NSMutableArray *)array1 secondArray: (NSMutableArray *)array2 { // 全为空不处理 if (!array1.

iOS实现高效裁剪图片圆角算法教程

前言 项目有个需求:裁剪图片,针对头像,下面是要求: 大家可以看到这张图片的圆角已经去除,下面说说我在项目利用了两种方式实现此裁剪以及查看技术文档发现更高效裁剪方式,下面一一讲解:看下来大约需要15-20分钟. 在公共类中Util类中创建类方法 1.CGContext裁剪 //CGContext裁剪 + (UIImage *)CGContextClip:(UIImage *)img cornerRadius:(CGFloat)c; 实现该方法: // CGContext 裁剪 + (UIImag

IOS面试大全之常见算法

这篇文字给大家分享了IOS面试中熟悉常见的算法,下面来一起看看吧. 1. 对以下一组数据进行降序排序(冒泡排序)."24,17,85,13,9,54,76,45,5,63" int main(int argc, char *argv[]) { int array[10] = {24, 17, 85, 13, 9, 54, 76, 45, 5, 63}; int num = sizeof(array)/sizeof(int); for(int i = 0; i < num-1; i

iOS中排列组合算法的使用小结

前言 最近在项目中用到了排列组合计算,虽然比较简单,但是整个学习过程还是要记录下来的,以便以后可以吸取经验. 一般来说,排列组合就等于搜索. 注意点: 1.去重复:规定子集顺序必须升序: 2.候选数组的结果处理.必须深拷贝,否则最后的结果集里全是空的(加了一堆指针). 3.在写递归的时候(DFS:深度优先搜索),思路是先把以 1 开头的都找出来,再把 2 开头的都找出来 -- 所有在递归之前做过的事情,之后都要把它抹回来.递归做的事情能一句话描述清楚.递归就是不断地把规模变小,但是都做的一件事情

iOS中MD5加密算法的介绍和使用

前言 软件开发过程中,对数据进行加密是保证数据安全的重要手段,常见的加密有Base64加密和MD5加密.Base64加密是可逆的,MD5加密目前来说一般是不可逆的. MD5生成的是固定的128bit,即128个0和1的二进制位,而在实际应用开发中,通常是以16进制输出的,所以正好就是32位的16进制,说白了也就是32个16进制的数字. MD5主要特点是 不可逆,相同数据的MD5值肯定一样,不同数据的MD5值不一样(也不是绝对的,但基本是不能一样的). MD5算法还具有以下性质: 1.压缩性:任意

浅谈iOS中的锁的介绍及使用

在平时的开发中经常使用到多线程,在使用多线程的过程中,难免会遇到资源竞争的问题,那我们怎么来避免出现这种问题那? 线程安全是什么? 当一个线程访问数据的时候,其他的线程不能对其进行访问,直到该线程访问完毕.简单来讲就是在同一时刻,对同一个数据操作的线程只有一个.只有确保了这样,才能使数据不会被其他线程影响.而线程不安全,则是在同一时刻可以有多个线程对该数据进行访问,从而得不到预期的结果. 比如写文件和读文件,当一个线程在写文件的时候,理论上来说,如果这个时候另一个线程来直接读取的话,那么得到的结

iOS开发中指纹识别简单介绍

ios开发中指纹识别简单介绍,在iphone系列中,是从5S以后开始有了指纹识别的功能,在ios8的时候开放的指纹验证的接口. 所以我们在进行指纹识别应用的时候要去判断机型以及系统的版本. 代码如下,下面需要特别注意的其实就是LAPolicyDeviceOwnerAuthentication和LAPolicyDeviceOwnerAuthenticationWithBiometrics的区别,以及检测系统的版本通过[UIDevice currentDevice].systemVersion.fl

iOS中NSNumberFormatter的介绍与用法

前言 iOS中NSDateFormatter用的范围一般来说比较广泛,不过相对于处理数字而言,很少用到NSNumberFormatter,NSNumberFormatter中有很多枚举类型,会为实际开发节省时间. NSNumberFormatter可以用来处理NSString和NSNumber之间的转化,可以满足基本的数字形式的转化.下面话不多说了,来一起看看详细的介绍吧 1:使用+ localizedStringFromNumber:numberStyle:本地化方法格式化NSNumber到N

iOS中常见的几种加密方法总结

前言 在我们日常开发中,加密是必不可少的一部分,而普通加密方法是讲密码进行加密后保存到用户偏好设置中,钥匙串是以明文形式保存,但是不知道存放的具体位置,下面本文将详细给大家介绍iOS中常见的几种加密方法,下面话不多说了,来一起看看详细的介绍吧. 一. base64加密 base64 编码是现代密码学的基础 基本原理: 原本是 8个bit 一组表示数据,改为 6个bit一组表示数据,不足的部分补零,每 两个0 用 一个 = 表示 用base64 编码之后,数据长度会变大,增加了大约 1/3 左右.

iOS中关于模块化开发解决方案(纯干货)

关于iOS模块化开发解决方案网上也有一些介绍,但真正落实在在具体的实例却很少看到,计划编写系统文章来介绍关于我对模块化解决方案的理解,里面会有包含到一些关于解耦.路由.封装.私有Pod管理等内容:并编写的一个实例项目放在git进行开源[jiaModuleDemo],里面现在已经放着一些封装的功能模块:会不断的进行更新,假如你感兴趣可以Star一下,项目也不断的更新完善优化:如果你有更好的方案或者说好的建议可以lssues,我会在短时间进行更新并修改相应的问题: 一:项目中存在的问题 1:当公司里

iOS 中根据屏幕宽度自适应分布按钮的实例代码

下载demo链接:https://github.com/MinLee6/buttonShow.git 屏幕摆放的控件有两种方式,一种根据具体内容变化,一种根据屏幕宽度变化. 下面我分别将两个方式,用代码的方式呈现: 1:根据具体内容变化 // // StyleOneViewController.m // buttonShow // // Created by limin on 15/06/15. // Copyright © 2015年 信诺汇通信息科技(北京)有限公司. All rights

IOS中使用UIWebView 加载网页、文件、 html的方法

UIWebView 是用来加载加载网页数据的一个框.UIWebView可以用来加载pdf word doc 等等文件 生成webview 有两种方法: 1.通过storyboard 拖拽 2.通过alloc init 来初始化 创建webview,下列文本中 _webView.dataDetectorTypes = UIDataDetectorTypeAll; 是识别webview中的类型,例如 当webview中有电话号码,点击号码就能直接打电话 - (UIWebView *)webView

iOS中Navbar设置渐变色效果的方法示例

本文主要给大家介绍了关于iOS中Navbar设置渐变色效果的相关内容,分享出来供大家参考学习,下面来看看详细的介绍吧. 设置渐变色 #import "NavigationViewController.h" #define LBColor(r, g, b) [UIColor colorWithRed:(r)/255.0 green:(g)/255.0 blue:(b)/255.0 alpha:1.0] @interface NavigationViewController () @end

iOS中关于Swift UICollectionView横向分页的问题

下面通过图文并茂的形式给大家介绍UICollectionView横向分页的问题,具体内容详情如下所示: 情况 直接看图 滚前 滚后 已经设置collectionView的isPagingEnabled为true了,可是出现了这种情况,原因就是collectionView的contentSize不够. <UICollectionView: 0x7fc565076000; frame = (0 0; 375 197); clipsToBounds = YES; gestureRecognizers