Java 中的范围和计数问题

2025年3月17日 | 阅读11分钟

给定一个包含负数和非负数的数组 numArr[]，大小为 S。还提供了两个数字 ‘left’ 和 ‘right’。我们的任务是返回区间和的数量，使得该和介于 left 和 right 之间（包括 left 和 right），其中 left <= right。区间和 R(l, r) 表示 numArr[] 中索引 l 到 r 之间的数字之和，其中 l 必须小于或等于 r。

示例 1

输入: numArr[] = {1, 2, 3, 4, 5, 6, 7}, left = 2, right = 7

输出: 有 10 个区间，其和介于 2 和 7 之间。

解释: 让我们看看不同子数组的区间和。

从第 0 个索引开始

R[0, 0] 为 1 = 1 R[0, 1] = 1 + 2 = 3 R[0, 2] = 1 + 2 + 3 = 6

R[0, 3] = 1 + 2 + 3 + 4 = 10 R[0, 4] = 1 + 2 + 3 + 4 + 5 = 15

R[0, 5] = 1 + 2 + 3 + 4 + 5 + 6 = 21 R[0, 6] = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28

从第 1 个索引开始

R[1, 1] 为 2 = 2 R[1, 2] = 2 + 3 = 5 R[1, 3] = 2 + 3 + 4 = 9

R[1, 4] = 2 + 3 + 4 + 5 = 14 R[1, 5] = 2 + 3 + 4 + 5 + 6 = 20

R[1, 6] = 2 + 3 + 4 + 5 + 6 + 7 = 27

从第 2 个索引开始

R[2, 2] 为 3 = 3 R[2, 3] = 3 + 4 = 7 R[2, 4] = 3 + 4 + 5 = 12

R[2, 5] = 3 + 4 + 5 + 6 = 18 R[2, 6] = 3 + 4 + 5 + 6 + 7 = 25

从第 3 个索引开始

R[3, 3] 为 4 = 4 R[3, 4] = 4 + 5 = 9 R[3, 5] = 4 + 5 + 6 = 15

R[3, 6] = 4 + 5 + 6 + 7 = 22

从第 4 个索引开始

R[4, 4] 为 5 = 5 R[4, 5] = 5 + 6 = 11 R[4, 6] = 5 + 6 + 7 = 18

从第 5 个索引开始

R[5, 5] 为 6 = 6 R[5, 6] = 6 + 7 = 13

从第 6 个索引开始

R[6, 6] 为 7 = 7

下图显示了相同的情况。

在所有这些区间中，只有 R[0, 1], R[0, 2], R[1, 1], R[1, 2], R[2, 2], R[2, 3], R[3, 3], R[4, 4], R[5, 5], 和 R[6, 6] 介于 2 到 7 之间。因此，总共有 7 个区间和在 2 到 7 之间（包括两端）。因此，答案是 7。

示例 2

输入: numArr[] = {11, 12, 13, 14, 15, 16, 17}, left = 9, right = 10

输出: 没有区间的和介于 13 和 20 之间。

解释: 让我们看看不同子数组的区间和。

从第 0 个索引开始

R[0, 0] 为 11 = 11 R[0, 1] = 11 + 12 = 23 R[0, 2] = 11 + 12 + 13 = 36

R[0, 3] = 11 + 12 + 13 + 14 = 50 R[0, 4] = 11 + 12 + 13 + 14 + 15 = 65

R[0, 5] = 11 + 12 + 13 + 14 + 15 + 16 = 81 R[0, 6] = 11 + 12 + 13 + 14 + 15 + 16 + 17 = 98

从第 1 个索引开始

R[1, 1] 为 12 = 12 R[1, 2] = 12 + 13 = 25 R[1, 3] = 12 + 13 + 14 = 39

R[1, 4] = 12 + 13 + 14 + 15 = 54 R[1, 5] = 12 + 13 + 14 + 15 + 16 = 70

R[1, 6] = 12 + 13 + 14 + 15 + 16 + 17 = 87

从第 2 个索引开始

R[2, 2] 为 13 = 13 R[2, 3] = 13 + 14 = 27 R[2, 4] = 13 + 14 + 15 = 42

R[2, 5] = 13 + 14 + 15 + 16 = 58 R[2, 6] = 13 + 14 + 15 + 16 + 17 = 75

从第 3 个索引开始

R[3, 3] 为 14 = 14 R[3, 4] = 14 + 15 = 29 R[3, 5] = 14 + 15 + 16 = 45

R[3, 6] = 14 + 15 + 16 + 17 = 62

从第 4 个索引开始

R[4, 4] 为 15 = 15 R[4, 5] = 15 + 16 = 31 R[4, 6] = 15 + 16 + 17 = 48

从第 5 个索引开始

R[5, 5] 为 16 = 16 R[5, 6] = 16 + 17 = 33

从第 6 个索引开始

R[6, 6] 为 17 = 17

下图显示了相同的情况。

在所有这些区间中，没有一个区间的和介于 9 到 10 之间。因此，总共有 0 个区间和在 9 到 10 之间（包括两端）。

朴素方法

直接或朴素的方法是找出输入数组的所有子数组。之后，过滤掉那些和在（left 到 right）范围内的子数组。

算法

步骤 1: 初始化变量 count = 0, tmp = 0。

步骤 2: 迭代 j 从 0 到输入数组的长度 - 1。这是为了确定我们子数组的起始点。

在此循环的每次迭代中更新 tmp = 0。
迭代 i 从 j 到输入数组的长度 - 1。这将确定我们子数组的结束点。
更新 tmp 为 tmp = tmp + numArr[i];
如果 tmp >= left 或 tmp <= right，则将 count 变量加 1。

步骤 3: 返回 count。

实施

观察上述算法的实现。

文件名: CountRangeSum.java

public class CountRangeSum 
{
// a method that computes the count of ranges (subarrays) whose
// sum lies in the range left and right (left and right inclusive)
public int findCountRangeSum(int numArr[], int size, int left, int right)
{
long tmp = 0;
int count = 0;

// Checking all of the subarrays
// that can be made from the input array numArr[]
for (int j = 0; j < size; j++)
{
tmp = 0;
for (int i = j; i < size; i++)
{
// the sub-array starts from the jth index and 
// goes till the ith index
// as the ith index changes in each iteration, the size of the sub 
// array also changes, and hence, the sum also changes in each iteration
// and these changes are reflected or kept in the tmp variable
tmp = tmp + numArr[i];

// If the sum is present within the range, then increment the count by 1
if(tmp >= left && tmp <= right)
{
count = count + 1;
}
}
}
return count;
}

// main method
public static void main(String argvs[])
{
// creating an object of the class CountRangeSum
CountRangeSum obj = new CountRangeSum();

// input array
int numArr[] = {1, 2, 3, 4, 5, 6, 7};

// computing its size
int size = numArr.length;

// defining the ranges, i.e, the left and the right boundary 
int left = 2;
int right = 7;

// invoking the method findCountRangeSum() and storing the answer
int ans = obj.findCountRangeSum(numArr, size, left, right);

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(numArr[i] + " ");    
}
System.out.println();

if(ans != 0)
{
System.out.print("The number of ranges whose sum lies between "+ left + " & " + right + " is " + ans + ".");
}
else
{
System.out.print("There is no range whose sum lies between "+ left + " & " + right + ".");    
}

System.out.println("\n");

// input array
int numArr1[] = {11, 12, 13, 14, 15, 16, 17};

// computing its size
size = numArr1.length;

// defining the ranges, i.e, the left and the right boundary 
left = 9;
right = 10;

// invoking the method findCountRangeSum() and storing the answer
ans = obj.findCountRangeSum(numArr1, size, left, right);

System.out.println("For the input array: ");

for(int i = 0; i < size; i++)
{
System.out.print(numArr1[i] + " ");    
}
System.out.println();

if(ans != 0)
{
System.out.print("The number of ranges whose sum lies between "+ left + " & " + right + " is " + ans + ".");
}
else
{
System.out.print("There is no range whose sum lies between "+ left + " & " + right + ".");    
}
}

}

输出

For the input array: 
1 2 3 4 5 6 7 
The number of ranges whose sum lies between 2 & 7 is 10.

For the input array: 
11 12 13 14 15 16 17 
There is no range whose sum lies between 9 & 10.

复杂度分析: 我们使用了嵌套的 for 循环来计算答案。因此，程序的 time complexity 为 O(n²)，其中 n 是数组中元素的总数。另外，我们没有使用任何数据结构来保存结果。因此，程序的 space complexity 是常数，即 O(1)。

高效方法

在此方法中，我们将尝试将程序的 time complexity 从 O(n2) 降低。在此解决方案中，借助归并排序，我们在归并过程中计算答案。在归并阶段，我们已经对左半部分 [start, mid) 和右半部分 [mid, end) 进行了排序。然后我们用索引 i 遍历左半部分。对于每个 i，需要计算右半部分中的两个索引 m 和 n，其中 n 是第一个满足 sumArr[n] - sumArr[i] <= right 的索引，k 是第一个满足 sumArr[m] - sumArr[i] < left 的索引。那么，[left, right] 中的总和数为 n - m。

观察以下算法。

算法

步骤 1: 定义一个方法，该方法使用归并排序计算和在范围 [left, right] 内的子数组的数量，该方法为 int mergeCount(int sumArr[], int left, int right, int st, int ed)。

步骤 2: 处理基本情况：当 ed - st <= 1 时，返回 0。

步骤 3: 初始化一些变量 int mid = (st + ed) / 2; int m = mid; int n = mid;

步骤 4: 初始化另一个名为 count 的变量，并将 count 更新为，count = mergeCount (sumArr, left, right, st, mid) + mergeCount(sumArr, left, right, mid, ed)

步骤 5: 迭代 j 从 st 到 mid。

While(m < ed and sumArr[m] - sumArr[j] < left) m = m + 1;

while(n < ed and sumArr[n] - sumArr[j] <= right) n = n + 1;

将 count 更新为 count = count + n - m。

步骤 6: 对 sumArr 从 st 到 ed 进行排序。

步骤 7: 返回 count。

实施

观察上述算法的实现。

文件名: CountRangeSum1.java

// important import statement
import java.util.Arrays;
    
    public class CountRangeSum1 
    {
    static int mergeCount(int sumArr[], int left, int right, int st, int ed)
    {
    // handling the base case case
    if (ed - st <= 1)
    {
    return 0;
    }
    
    int mid = (st + ed) / 2;
    int m = mid;
    int n = mid;
    int count = mergeCount(sumArr, left, right, st, mid) + mergeCount(sumArr, left, right, mid, ed);
    
    // loop for Counting the valid ranges
    for (int j = st; j < mid; j++)
    {
    while (m < ed && sumArr[m] - sumArr[j] < left)
    {
    m = m + 1;
    }    
    while (n < ed && sumArr[n] - sumArr[j] <= right)
    {
    n = n + 1;
    }
    count = count + n - m;
    } 
    // merging the two sorted halves and copying the result that is sorted back to the array sumArr[]
    Arrays.sort(sumArr, st, ed);
    return count;
    }
    public static int findCountRangeSum(int numArr[], int size, int left, int right)
    {
    int sumArr[] = new int[size + 1];    
    // initializing the elements of the array sumArr[] to 0
    for (int i = 0; i < size + 1; i++)
    {
    sumArr[i] = 0; 
    }
    // loop for computing the prefix sum
    // it is done so that the we can compute the range sum quickly
    for (int j = 0; j < size; j++)
    {
    sumArr[j + 1] = sumArr[j] + numArr[j];
    }
    return mergeCount(sumArr, left, right, 0, size + 1);
    }
    
    // main method
    public static void main(String argvs[])
    {
    // creating an object of the class CountRangeSum1
    CountRangeSum1 obj = new CountRangeSum1();
    
    // input array
    int numArr[] = {1, 2, 3, 4, 5, 6, 7};
    
    // computing its size
    int size = numArr.length;
    
    // defining the ranges, i.e, the left and the right boundary 
    int left = 2;
    int right = 7;
    
    // invoking the method findCountRangeSum() and storing the answer
    int ans = obj.findCountRangeSum(numArr, size, left, right);
    
    System.out.println("For the input array: ");
    
    for(int i = 0; i < size; i++)
    {
    System.out.print(numArr[i] + " ");    
    }
    System.out.println();
    
    if(ans != 0)
    {
    System.out.print("The number of ranges whose sum lies between "+ left + " & " + right + " is " + ans + ".");
    }
    else
    {
    System.out.print("There is no range whose sum lies between "+ left + " & " + right + ".");    
    }
    
    System.out.println("\n");
    
    // input array
    int numArr1[] = {11, 12, 13, 14, 15, 16, 17};
    
    // computing its size
    size = numArr1.length;
    
    // defining the ranges, i.e, the left and the right boundary 
    left = 9;
    right = 10;
    
    // invoking the method findCountRangeSum() and storing the answer
    ans = obj.findCountRangeSum(numArr1, size, left, right);
    
    System.out.println("For the input array: ");
    
    for(int i = 0; i < size; i++)
    {
    System.out.print(numArr1[i] + " ");    
    }
    System.out.println();
    
    if(ans != 0)
    {
    System.out.print("The number of ranges whose sum lies between "+ left + " & " + right + " is " + ans + ".");
    }
    else
    {
    System.out.print("There is no range whose sum lies between "+ left + " & " + right + ".");    
    }
    }
    
    }

输出

For the input array: 
1 2 3 4 5 6 7 
The number of ranges whose sum lies between 2 & 7 is 10.

For the input array: 
11 12 13 14 15 16 17 
There is no range whose sum lies between 9 & 10.

复杂度分析: 我们使用了归并排序技术。因此，上述程序的 time complexity 为 O(n * log(n))。另外，我们使用了辅助数组 sumArr[]。因此，上述程序的 space complexity 为 O(n)，其中 n 是输入数组中元素的总数。

下一个主题Java 中创建互质树

← 上一个下一个 →

Java 中的范围和计数问题

示例 1

示例 2

朴素方法

算法

实施

高效方法

算法

实施

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Java 程序

Java 中的范围和计数问题

示例 1

示例 2

朴素方法

算法

实施

高效方法

算法

实施

相关帖子

Keith Number in Java

如何在 Java 中将十进制转换为十六进制

Java 中的交错字符串问题

如何在 Java 中将 double 转换为 int

在控制台上打印以下图案的 Java 程序 5

Java 查找字符串所有子集的程序

Java 从循环链表中间删除节点的程序

将字符串中的空格替换为特定字符的 Java 程序

Evil Number Java

如何在 Java 中将 int 转换为 double

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器