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

难度:

标签:

题目描述

Given a 0-indexed integer array nums of length n and an integer target, return the number of pairs (i, j) where 0 <= i < j < n and nums[i] + nums[j] < target.

Example 1:

Input: nums = [-1,1,2,3,1], target = 2
Output: 3
Explanation: There are 3 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = 0 < target
- (0, 2) since 0 < 2 and nums[0] + nums[2] = 1 < target 
- (0, 4) since 0 < 4 and nums[0] + nums[4] = 0 < target
Note that (0, 3) is not counted since nums[0] + nums[3] is not strictly less than the target.

Example 2:

Input: nums = [-6,2,5,-2,-7,-1,3], target = -2
Output: 10
Explanation: There are 10 pairs of indices that satisfy the conditions in the statement:
- (0, 1) since 0 < 1 and nums[0] + nums[1] = -4 < target
- (0, 3) since 0 < 3 and nums[0] + nums[3] = -8 < target
- (0, 4) since 0 < 4 and nums[0] + nums[4] = -13 < target
- (0, 5) since 0 < 5 and nums[0] + nums[5] = -7 < target
- (0, 6) since 0 < 6 and nums[0] + nums[6] = -3 < target
- (1, 4) since 1 < 4 and nums[1] + nums[4] = -5 < target
- (3, 4) since 3 < 4 and nums[3] + nums[4] = -9 < target
- (3, 5) since 3 < 5 and nums[3] + nums[5] = -3 < target
- (4, 5) since 4 < 5 and nums[4] + nums[5] = -8 < target
- (4, 6) since 4 < 6 and nums[4] + nums[6] = -4 < target

Constraints:

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

代码结果

运行时间: 24 ms, 内存: 15.9 MB

/*
 * Approach:
 * Similar to the previous solution, we can use Java Streams to achieve the same result.
 * We will use IntStream to iterate over the pairs and filter out the ones that satisfy the condition.
 */
import java.util.stream.IntStream;

public class Solution {
    public int countPairs(int[] nums, int target) {
        int n = nums.length;
        return (int) IntStream.range(0, n)
                .flatMap(i -> IntStream.range(i + 1, n)
                        .filter(j -> nums[i] + nums[j] < target))
                .count();
    }
}

解释

方法:

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

时间复杂度:

O(n^2)

空间复杂度:

O(1)

代码细节讲解

🦆

在题解中，没有提到对输入数组`nums`进行排序的步骤。排序是否对算法的正确性或效率有影响？如果有，怎样的排序可能改进效率？

▷

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

🦆

在暴力法的基础上，是否存在更优的算法来减少必要的比较次数，例如使用双指针或哈希表？如果存在，请简述其基本思路。

▷

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

🦆

题解中计数器`ans`是如何确保不重复计算满足条件的下标对的？

▷

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

🦆

对于边界情况如数组`nums`为空或只有一个元素，题解的算法是否能正确处理？如果不能，应如何修改？

▷

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

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

题目描述

代码结果

解释

代码细节讲解

相关问题