IOS 三数之和求解 IOS 算法 三数之和求解问题
ShawnAlex 人气:0想了解IOS 算法 三数之和求解问题的相关内容吗,ShawnAlex在本文为您仔细讲解IOS 三数之和求解的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点: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、代码
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]]
加载全部内容