统计和小于目标的下标对数目

难度: 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

Submission

运行时间: 24 ms

内存: 15.9 MB

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        left = 0
        n = len(nums)
        ans = 0
        while left < n:
            right = left + 1
            while right < n:
                if nums[left] + nums[right] < target:
                    ans +=1
                right +=1
            left += 1
        return ans

Explain

该题解采用了暴力法来寻找所有满足条件的下标对。它首先使用一个外层循环，遍历数组中的每个元素作为第一个下标i（从0开始至n-2），然后使用一个内层循环，对于每个i，遍历其后的元素作为第二个下标j（从i+1开始至n-1）。对于每对下标i和j，它检查nums[i] + nums[j]是否小于目标值target。如果是，则累加到结果计数器ans中。

时间复杂度: O(n^2)

空间复杂度: O(1)

class Solution:
    def countPairs(self, nums: List[int], target: int) -> int:
        left = 0 # 初始化左指针
        n = len(nums) # 获取数组的长度
        ans = 0 # 初始化答案计数器
        while left < n: # 外层循环，遍历每个作为第一个元素的可能的i
            right = left + 1 # 初始化右指针，始终位于left的右侧
            while right < n: # 内层循环，遍历每个作为第二个元素的可能的j
                if nums[left] + nums[right] < target: # 检查元素对之和是否小于目标值
                    ans +=1 # 如果是，计数器加一
                right +=1 # 移动右指针
            left += 1 # 移动左指针
        return ans # 返回满足条件的对数

Explore

在该题解中，没有进行排序因为暴力法的本质是检查所有可能的下标对，而排序与否不影响其正确性。然而，对数组进行排序可以提高算法的效率。通过排序，可以应用双指针技术，一个指针从数组起始位置向右移动，另一个指针从数组末端向左移动，这样可以在O(n)的时间内检查并统计所有满足条件的对，从而避免O(n^2)的复杂度。

存在更优的算法，如使用双指针或哈希表。在使用双指针的方法中，首先对数组进行排序，然后使用两个指针，一个指向数组的开始，另一个指向数组的末尾。当两指针的和小于目标值时，因为数组是有序的，可以直接将左指针右移以增大和；如果和大于目标值，则将右指针左移以减小和。另一种方法是使用哈希表来记录每个元素出现的次数，然后对每个元素，计算与其配对后能达到目标值的元素是否存在于哈希表中，这可以在接近O(n)的时间内完成。

在题解中，外层循环的指针`left`从0开始至数组倒数第二个元素，内层循环的指针`right`从`left`的下一个元素开始至数组末尾。这种遍历方式确保每对下标(i, j)只会被考虑一次，且i总是小于j，从而避免了重复计算相同的下标对。

当前算法可以正确处理数组为空的情况，因为外层循环和内层循环都不会开始执行，结果自然是0。但对于只有一个元素的数组，同样不会进入内层循环，因此结果也是0，符合题目要求。因此，该算法已经能够正确处理这些边界情况。