LeetCode第259题：较小的三数之和

题目描述

给定一个长度为 n 的整数数组 nums 和一个目标值 target，寻找能够使条件 nums[i] + nums[j] + nums[k] < target 成立的三元组 i, j, k 个数（0 <= i < j < k < n）。

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

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

示例 2：

输入: nums = [], target = 0
输出: 0

示例 3：

输入: nums = [0], target = 0
输出: 0

提示

• n == nums.length
• 0 <= n <= 300
• -100 <= nums[i] <= 100
• -100 <= target <= 100

解题思路

本题要求找出数组中三个元素之和小于目标值的三元组数量。这道题是三数之和的变种，可以使用排序加双指针的方法解决。

方法一：暴力法（超时）

最直接的方法是使用三重循环遍历所有可能的三元组，判断它们的和是否小于目标值。

for i in range(0, n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if nums[i] + nums[j] + nums[k] < target:
                count += 1

时间复杂度：O(n³)，其中n是数组长度。 空间复杂度：O(1)。

方法二：排序 + 双指针

更高效的方法是先对数组进行排序，然后使用双指针技巧：

1. 对数组进行排序
2. 固定第一个元素，使用双指针遍历剩余数组
3. 当三数之和小于目标值时，右指针到左指针之间的所有元素都可以与左指针组成符合条件的三元组

具体步骤：

1. 对数组 nums 进行排序
2. 初始化计数器 count = 0
3. 遍历数组，固定第一个元素 nums[i]
4. 对于每个 nums[i]，设置左指针 left = i+1 和右指针 right = n-1
5. 当 left < right 时：
   • 如果 nums[i] + nums[left] + nums[right] < target，那么从 left+1 到 right 的所有元素都可以和 nums[i] 与 nums[left] 组成满足条件的三元组，所以 count += right - left，然后 left++
   • 否则，right--
6. 返回 count

时间复杂度：O(n²)，其中n是数组长度。排序需要O(n log n)的时间，双指针遍历需要O(n²)的时间。 空间复杂度：O(log n)，排序所需的空间。

代码实现

C# 实现

public class Solution {
    public int ThreeSumSmaller(int[] nums, int target) {
        // 对数组进行排序
        Array.Sort(nums);
        int count = 0;
        int n = nums.Length;
        
        // 固定第一个元素，然后使用双指针
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    // 从left+1到right的所有元素都可以和nums[i]与nums[left]组成满足条件的三元组
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return count;
    }
}

Python 实现

class Solution:
    def threeSumSmaller(self, nums: List[int], target: int) -> int:
        # 对数组进行排序
        nums.sort()
        count = 0
        n = len(nums)
        
        # 固定第一个元素，然后使用双指针
        for i in range(n - 2):
            left, right = i + 1, n - 1
            
            while left < right:
                if nums[i] + nums[left] + nums[right] < target:
                    # 从left+1到right的所有元素都可以和nums[i]与nums[left]组成满足条件的三元组
                    count += right - left
                    left += 1
                else:
                    right -= 1
        
        return count

C++ 实现

class Solution {
public:
    int threeSumSmaller(vector<int>& nums, int target) {
        // 对数组进行排序
        sort(nums.begin(), nums.end());
        int count = 0;
        int n = nums.size();
        
        // 固定第一个元素，然后使用双指针
        for (int i = 0; i < n - 2; i++) {
            int left = i + 1;
            int right = n - 1;
            
            while (left < right) {
                if (nums[i] + nums[left] + nums[right] < target) {
                    // 从left+1到right的所有元素都可以和nums[i]与nums[left]组成满足条件的三元组
                    count += right - left;
                    left++;
                } else {
                    right--;
                }
            }
        }
        
        return count;
    }
};

执行结果

C# 实现

• 执行用时：136 ms
• 内存消耗：38.2 MB

Python 实现

• 执行用时：92 ms
• 内存消耗：15.8 MB

C++ 实现

• 执行用时：32 ms
• 内存消耗：9.9 MB

性能对比

语言	执行用时	内存消耗	特点
C#	136 ms	38.2 MB	语法清晰，性能较差
Python	92 ms	15.8 MB	实现简洁，性能适中
C++	32 ms	9.9 MB	性能最佳，内存占用最小

代码亮点

1. 🎯 使用排序加双指针的方法，将时间复杂度从O(n³)优化至O(n²)
2. 💡 在找到符合条件的三元组时，一次性计算了所有符合条件的组合数量，避免了重复计算
3. 🔍 在遍历过程中有效剪枝，当左指针超过右指针时结束当前循环

常见错误分析

1. 🚫 没有先对数组进行排序，导致双指针算法无法正常工作
2. 🚫 计算符合条件的三元组数量时，错误地只增加1，而不是增加right - left
3. 🚫 边界条件处理不当，例如数组长度小于3时没有返回0
4. 🚫 循环条件设置错误，例如i < n而不是i < n-2，可能导致索引越界

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
暴力法	O(n³)	O(1)	直观易懂	效率低，容易超时
排序+双指针	O(n²)	O(log n)	效率高，符合题目要求	需要先排序，改变原数组顺序
二分查找	O(n² log n)	O(log n)	思路清晰	相比双指针效率稍低

相关题目

• LeetCode 15. 三数之和 - 中等
• LeetCode 16. 最接近的三数之和 - 中等
• LeetCode 18. 四数之和 - 中等
• LeetCode 167. 两数之和 II - 输入有序数组 - 简单