0259. 较小的三数之和 #

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

题目大意 #

给定一个长度为 n 的整数数组和一个目标值 target。

要求：寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 (i, j, k) 的个数（0 <= i < j < k < n）。

注意：最好在 $O(n^2)$ 的时间复杂度内解决问题。

解题思路 #

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

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

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

代码 #

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15


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