跳至主要內容

0259. 较小的三数之和

ITCharge大约 2 分钟

0259. 较小的三数之和open in new window

  • 标签:数组、双指针、二分查找、排序
  • 难度:中等

题目链接

题目大意

描述:给定一个长度为 nn 的整数数组和一个目标值 targettarget

要求:寻找能够使条件 nums[i]+nums[j]+nums[k]<targetnums[i] + nums[j] + nums[k] < target 成立的三元组 (ii, jj, kk) 的个数(0<=i<j<k<n0 <= i < j < k < n)。

说明

  • 最好在 O(n2)O(n^2) 的时间复杂度内解决问题。
  • n==nums.lengthn == nums.length
  • 0n35000 \le n \le 3500
  • 100nums[i]100-100 \le nums[i] \le 100
  • 100target100-100 \le target \le 100

示例

  • 示例 1:
输入: nums = [-2,0,1,3], target = 2
输出: 2 
解释: 因为一共有两个三元组满足累加和小于 2:
     [-2,0,1]
     [-2,0,3]
  • 示例 2:
输入: nums = [], target = 0
输出: 0

解题思路

思路 1:排序 + 双指针

三元组直接枚举的时间复杂度是 O(n3)O(n^3),明显不符合题目要求。那么可以考虑使用双指针减少循环内的时间复杂度。具体做法如下:

  • 先对数组进行从小到大排序。
  • 遍历数组,对于数组元素 nums[i]nums[i],使用两个指针 leftleftrightrightleftleft 指向第 i+1i + 1 个元素位置,rightright 指向数组的最后一个元素位置。
  • 在区间 [left,right][left, right] 中查找满足 nums[i]+nums[left]+nums[right]<targetnums[i] + nums[left] + nums[right] < target的方案数。
  • 计算 nums[i]nums[i]nums[left]nums[left]nums[right]nums[right] 的和,将其与 targettarget 比较。
    • 如果 nums[i]+nums[left]+nums[right]<targetnums[i] + nums[left] + nums[right] < target,则说明 iileftleftrightright 作为三元组满足题目要求,同时说明区间 [left,right][left, right] 中的元素作为 rightright 都满足条件,此时将 leftleft 右移,继续判断。
    • 如果 nums[i]+nums[left]+nums[right]targetnums[i] + nums[left] + nums[right] \ge target,则说明 rightright 太大了,应该缩小 rightright,然后继续判断。
  • left==rightleft == right 时,区间搜索完毕,继续遍历 nums[i+1]nums[i + 1]

这种思路使用了两重循环,其中内层循环当 left==rightleft == right 时循环结束,时间复杂度为 O(n)O(n),外层循环时间复杂度也是 O(n)O(n)。所以算法的整体时间复杂度为 O(n2)O(n^2),符合题目要求。

思路 1:代码

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        nums.sort()
        size = len(nums)
        res = 0
        for i in range(size):
            left, right = i + 1, size - 1
            while left < right:
                total = nums[i] + nums[left] + nums[right]
                if total < target:
                    res += (right - left)
                    left += 1
                else:
                    right -= 1
        return res

思路 1:复杂度分析

  • 时间复杂度O(n2)O(n^2)
  • 空间复杂度O(logn)O(\log n)