LeetCoder 15. 3Sum

xiaoxiao2021-02-28  125

题意

一个数组,找到三个数,使其相加等于0,找出这些组合

思路

解法一: 暴力查找,三层循环寻找三个数,检查组合,时间复杂度 O(n3)

解法二: 理论上,只要找到两个数,那么第三个数也就确定是几了,只需要找到两个数,然后查找满足条件的第三个数是否存在就行了,如果存在,那么满足条件,进行组合,时间复杂度 O(n2)

解法三:

如果三个数相加为0,那么必定有三种情况

一个正数或者至少一个负数一个负数或者至少一个正数三者皆为0

第三种情况暂且不考虑,因为在进行检查前两种情况的过程中即可验证第三种情况,首先对序列进行排序,然后下标 i 0 length3 ,因为组合要三个数,下标k从 length1 开始,下标 j i 1 k1 ,然后下标 i 不变,j k ,进行变化,三者所对应序列中的数之和sum

sum==0 满足条件,可加入组合,但是同种组合应视为同一组合,所以说 j k应去寻找下一个不相同的位置的数 sum>0 说明 k 代表的数太大,所以说k减小 sum<0 说明 j 代表的数太小,所以说j增大

优化:因为实现对序列进行了排序,所以说可以确定下标 i 为三个数中最小的那一个,如果i对应的数>0,那么后面两个数必定也是大于0的,所以说,当 i 对应的数>0时,直接停止寻找.时间复杂度O(n2)

结果

Your runtime beats 46.15 % of swift submissions

代码

class Solution { func threeSum(_ nums: [Int]) -> [[Int]] { let len = nums.count var ans = [[Int]]() if len < 3 { return ans } var tempNums = nums tempNums.sort() for i in 0..<len - 2 { if i != 0 && tempNums[i] == tempNums[i - 1]{ continue } if tempNums[i] > 0 { break } var j = i + 1 var k = len - 1 while j < k { let sum = tempNums[i] + tempNums[j] + tempNums[k] if sum == 0 { let ansNums = [tempNums[i], tempNums[j], tempNums[k]] ans.append(ansNums) while j + 1 < k && tempNums[j] == tempNums[j + 1] { j += 1 } j += 1 while k - 1 > j && tempNums[k] == tempNums[k - 1] { k -= 1 } k -= 1 } else if sum < 0 { j += 1 } else { k -= 1 } } } return ans } }
转载请注明原文地址: https://www.6miu.com/read-50758.html

最新回复(0)