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中排列组合算法的使用小结

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

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

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

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

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

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

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

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

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

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

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

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常见算法以及应用知识点总结

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

IOS 常见内存泄漏以及解决方案

IOS 常见内存泄漏以及解决方案 整理了几个内存泄漏的例子,由于转载地址已经找不到了,在这里就不一一列出来了. 1 OC和CF转化出现的内存警告 CFStringRef cfString = CFURLCreateStringByAddingPercentEscapes(kCFAllocatorDefault,(CFStringRef)picDataString,NULL,CFSTR(":/?#[]@!$&'()*+,;="),kCFStringEncodingUTF8); N

IOS 常见的循环引用总结

IOS 常见的循环引用总结 介绍: 循环引用,指的是多个对象相互引用时,使得引用形成一个环形,导致外部无法真正是否掉这块环形内存.其实有点类似死锁. 举个例子:A->B->C->....->X->B   ->表示强引用,这样的B的引用计数就是2,假如A被系统释放了,理论上A会自动减小A所引用的资源,就是B,那么这时候B的引用计数就变成了1,所有B无法被释放,然而A已经被释放了,所有B的内存部分就肯定无法再释放再重新利用这部分内存空间了,导致内存泄漏. 情况一:deleg

JS常见算法详解

算法是程序的灵魂,一个优秀前端工程师对算法也是要有所了解的,本文总结了我们在开发.面试中经常会遇到的基础算法,使用原生JS实现,未必是最优解,可以互相探讨. 为了便于查看,简单分下类,本文也会持续更新. 排序算法 1. 冒泡排序 function bubbleSort(arr){ var i = j = 0; for(i=1;i<arr.length;i++){ for(j=0;j<=arr.length-i;j++){ var temp = 0; if(arr[j]>arr[j+1])

iOS常见的几个修饰词深入讲解

前言: 最近公司在扩招,做为公司仅有的唯一一个首席iOS开发工程师(手动滑稽),我不得不硬着头皮上阵. 然后却发现很多人的水平和年限严重不符,公司招的人都是3年+以上经验的人,然而这些人中有一半连修饰词的作用也说的模棱两可,加上自己水平也不高,对以后的职业生涯产生了严重的危机感,遂决定以后每周希望能写一篇有价值的文章,与君共勉,今天就说说iOS常见的几个修饰词. 一.readOnly,readWrite readOnly: 根据字面意思,大家都很容易知道是"只读"的意思,意味着只生成了

Python几种常见算法汇总

1.选择排序 选择排序是一种简单直观的排序算法.它的原理是这样:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的后面,以此类推,直到所有元素均排序完毕.算法实现如下: #找到最小的元素def FindSmall(list): min=list[0] for i in range(len(list)): if list[i]<min: min=list[i] return min #选择排序def Select_

JavaScript数组排序的六种常见算法总结

前言 着急用的话,选择前两个就行了,后面的看看就好. 开发中,遇到数组排序的需求很频繁,这篇文章会介绍几个常见排序思路. 一.希尔排序(性能最好) 如果要从大到小排列,则 while(arr[n] > arr[n - interval] && n > 0) . // 希尔排序算法 function xier(arr){ var interval = parseInt(arr.length / 2);//分组间隔设置 while(interval > 0){ for(var

ios常见加密解密方法(RSA、DES 、AES、MD5)

最近做了一个移动项目,是有服务器和客户端类型的项目,客户端是要登录才行的,服务器也会返回数据,服务器是用Java开发的,客户端要同时支持多平台(Android.iOS),在处理iOS的数据加密的时候遇到了一些问题.起初采取的方案是DES加密,老大说DES加密是对称的,网络抓包加上反编译可能会被破解,故采取RSA方式加密.RSA加密时需要公钥和私钥,客户端保存公钥加密数据,服务器保存私钥解密数据.(iOS端公钥加密私钥解密.java端公钥加密私钥解密,java端私钥加密公钥解密都容易做到,iOS不