求满足和小于给定值的数组三元组数量算法问题求助

嘿，你的思路方向完全没问题——固定第一个元素，把三元组问题拆解成**找剩余元素中两数之和小于(target - nums[i])**的二元组计数，这个拆解思路非常关键。不过我们可以结合排序+双指针来优化这个过程，把时间复杂度从暴力的O(n³)降到更高效的O(n²)，下面给你详细拆解：

具体实现步骤 #

1. 先对数组排序：排序后我们能利用有序数组的特性，用双指针快速统计符合条件的二元组数量，不用再暴力枚举所有可能。
2. 遍历每个元素作为第一个数：对于每个索引i，我们只需要在i+1到数组末尾的范围内，找所有j<k使得nums[j]+nums[k] < target - nums[i]。
3. 双指针统计二元组数量：
   • 初始化左指针left = i+1，右指针right = len(nums)-1
   • 如果nums[left] + nums[right] < target - nums[i]：说明从left到right-1的所有元素和nums[left]组合都满足条件，直接累加right - left个计数，然后左指针右移（尝试找更大的和）
   • 如果不满足，右指针左移（尝试减小当前两数之和）

用题目示例演示过程 #

nums排序后为[-2, 0, 1, 3]，target=2：

• 当i=0（nums[i]=-2），目标二元组和要小于2 - (-2)=4：
  • left=1，right=3：0+3=3<4，所以有3-1=2个符合条件的二元组（(0,1)和(0,3)），对应题目里的两个三元组
• 当i=1（nums[i]=0），目标二元组和要小于2-0=2：
  • left=2，right=3：1+3=4≥2，右指针左移到2，此时left=right，循环结束，没有符合条件的二元组
• i=2及之后的元素，剩余元素不足两个，直接跳过
  最终总计数为2，和题目结果一致。

Python代码实现 #

def threeSumSmaller(nums, target):
    nums.sort()
    count = 0
    n = len(nums)
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        current_target = target - nums[i]
        while left < right:
            if nums[left] + nums[right] < current_target:
                # 一次性统计所有符合条件的二元组
                count += right - left
                left += 1
            else:
                right -= 1
    return count

# 测试题目示例
print(threeSumSmaller([-2, 0, 1, 3], 2))  # 输出2

为什么这个方法更高效？ #

排序的时间复杂度是O(n log n)，外层遍历是O(n)，内层双指针遍历是O(n)，总时间复杂度为O(n²)，比暴力枚举的O(n³)效率提升非常明显；同时排序后还能避免很多重复的无效计算，让统计过程更顺畅。

内容的提问来源于stack exchange，提问作者mourinho