[Swift]LeetCode259.三数之和较小值$3SumSmaller

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：https://www.cnblogs.com/strengthen/p/10225825.html
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

给定n个整数nums和一个目标的数组，找出满足条件nums[i]+nums[j]+nums[k]<目标的索引三元组i、j、k的个数，其中0<=i<j<k<n。

例如，给定nums=[-2，0，1，3]和target=2。

返回2。因为有两个三元组的和小于2：

[-2, 0, 1]
[-2, 0, 3]

进阶：

你能在O（n2）运行时解决它吗？

 1 class Solution {
 2     func threeSumSmaller(_ nums:[Int],_ target:Int) -> Int{
 3         var nums = nums
 4         if nums.count < 3 {return 0}
 5         var res:Int = 0
 6         var n:Int = nums.count
 7         nums = nums.sorted(by:<)
 8         for i in 0..<(n - 2)
 9         {
10             var left:Int = i + 1
11             var right:Int = n - 1
12             while (left < right)
13             {
14                 if nums[i] + nums[left] + nums[right] < target
15                 {
16                     res += right - left
17                     left += 1
18                 }
19                 else
20                 {
21                     right -= 1
22                 }
23             }
24         }
25         return res
26     }
27 }