IOS 算法三数之和求解问题

2024-03-03 14:01:10

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系统库中定义了软件开发中常用的加解密算法,接口为C语言形式.具体包括了以下几个大类: #include <CommonCrypto/CommonCryptor.h> //常用加解密算法 #include <CommonCrypto/CommonDigest.h> //摘要算法 #include <CommonCrypto/CommonHMAC.h> #include <CommonCrypto/CommonKeyDerivation.h> #inclu
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面试中熟悉常见的算法,下面来一起看看吧. 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常用算法之两个有序数组合并（要求时间复杂度为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实现高效裁剪图片圆角算法教程

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

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

目录题目解题思路题目 15. 三数之和给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=
关于PHP求解三数之和问题详析

三数之和给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/3sum 解题思路
Python三数之和的实现方式

目录三数之和题目描述思路 Python3代码三数之和题目描述给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c , 使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组. 答案中不允许包含重复的三元组. 示例: 给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ] 思路 1. 首先将数组排序,可以利用Python内置函数,也可
C++实现LeetCode（三数之和）

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut
C++实现LeetCode(16.最近三数之和)

[LeetCode] 16. 3Sum Closest 最近三数之和 Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly on
JS求解两数之和算法详解

本文实例讲述了JS求解两数之和算法.分享给大家供大家参考,具体如下: 题目描述给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. ::: tip 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] ::: 解法利用 Map 记录数组元素值和对应的下标,对于一个数 nums[i],判断 target - num
使用python实现两数之和的画解算法

题目描述给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出和为目标值 target 的那两个整数,并返回它们的数组下标. 你可以假设每种输入只会对应一个答案.但是,数组中同一个元素在答案里不能重复出现. 你可以按任意顺序返回答案. 示例 1: 输入:nums = [2,7,11,15], target = 9 输出:[0,1] 解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] . 示例 2: 输入:nums = [3,2,4],
图解Java排序算法之快速排序的三数取中法

目录基本步骤三数取中根据枢纽值进行分割代码实现总结基本步骤三数取中在快排的过程中,每一次我们要取一个元素作为枢纽值,以这个数字来将序列划分为两部分.在此我们采用三数取中法,也就是取左端.中间.右端三个数,然后进行排序,将中间数作为枢纽值. 根据枢纽值进行分割代码实现 package sortdemo; import java.util.Arrays; /** * Created by chengxiao on 2016/12/14. * 快速排序 */ public class

IOS 算法 三数之和求解问题

目录