Easy

题目描述

给你一个下标从 0 开始长度为 n 的整数数组 nums 和一个整数 target ，请你返回满足 0 <= i < j < n 且 nums[i] + nums[j] < target 的数对 (i, j) 的数目。

示例 1：

输入：nums = [-1,1,2,3,1], target = 2
输出：3
解释：总共有 3 个数对满足题目要求：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = 0 < target
- (0, 2) ，0 < 2 且 nums[0] + nums[2] = 1 < target 
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = 0 < target
注意 (0, 3) 不计入答案，因为 nums[0] + nums[3] 不是严格小于 target 。

示例 2：

输入：nums = [-6,2,5,-2,-7,-1,3], target = -2
输出：10
解释：总共有 10 个数对满足题目要求：
- (0, 1) ，0 < 1 且 nums[0] + nums[1] = -4 < target
- (0, 3) ，0 < 3 且 nums[0] + nums[3] = -8 < target
- (0, 4) ，0 < 4 且 nums[0] + nums[4] = -13 < target
- (0, 5) ，0 < 5 且 nums[0] + nums[5] = -7 < target
- (0, 6) ，0 < 6 且 nums[0] + nums[6] = -3 < target
- (1, 4) ，1 < 4 且 nums[1] + nums[4] = -5 < target
- (3, 4) ，3 < 4 且 nums[3] + nums[4] = -9 < target
- (3, 5) ，3 < 5 且 nums[3] + nums[5] = -3 < target
- (4, 5) ，4 < 5 且 nums[4] + nums[5] = -8 < target
- (4, 6) ，4 < 6 且 nums[4] + nums[6] = -4 < target

提示：

  • 1 <= nums.length == n <= 50
  • -50 <= nums[i], target <= 50

解题思路

这道题要求统计数组中所有满足 i < j 且 nums[i] + nums[j] < target 的数对数量。

方法一：暴力枚举（推荐） 由于题目的数据规模很小（n ≤ 50），我们可以直接使用双重循环枚举所有可能的数对。外层循环枚举第一个元素的位置 i，内层循环枚举第二个元素的位置 j（j > i），如果两数之和小于目标值，则计数器加一。时间复杂度为 O(n²)，在当前约束下完全可以接受。

方法二：排序 + 双指针 我们也可以先对数组进行排序，然后使用双指针技巧。左指针指向数组开头，右指针指向数组末尾。如果当前两数之和小于目标值，说明左指针到右指针之间的所有元素与左指针指向的元素组成的数对都满足条件，因此答案加上 right - left，然后左指针右移；否则右指针左移。

虽然双指针方法在大规模数据下更优，但在本题的小数据规模下，暴力解法更简单直观，且性能差异可以忽略。

代码实现

class Solution {
public:
    int countPairs(vector<int>& nums, int target) {
        int count = 0;
        int n = nums.size();
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] < target) {
                    count++;
                }
            }
        }
        
        return count;
    }
};

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        count = 0
        n = len(nums)
        
        for i in range(n):
            for j in range(i + 1, n):
                if nums[i] + nums[j] < target:
                    count += 1
        
        return count

public class Solution {
    public int CountPairs(IList<int> nums, int target) {
        int count = 0;
        int n = nums.Count;
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[i] + nums[j] < target) {
                    count++;
                }
            }
        }
        
        return count;
    }
}

var countPairs = function(nums, target) {
    let count = 0;
    const n = nums.length;
    
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (nums[i] + nums[j] < target) {
                count++;
            }
        }
    }
    
    return count;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

解法时间复杂度空间复杂度
暴力枚举O(n²)O(1)
排序 + 双指针O(n log n)O(1)

相关题目