寻找给定和的子阵的 Java 程序–集合 1(非负数)
原文:https://www . geeksforgeeks . org/Java-用于查找的程序-具有给定和集 1 的子数组-非负数/
给定一个非负整数的未排序数组，找到一个与给定数字相加的连续子数组。 例:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Output: Sum found between indexes 2 and 4
Sum of elements between indices
2 and 4 is 20 + 3 + 10 = 33
Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Output: Sum found between indexes 1 and 4
Sum of elements between indices
1 and 4 is 4 + 0 + 0 + 3 = 7
Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
There is no subarray with 0 sum
可能有多个以和作为给定和的子阵列。以下解决方案首先打印这样的子阵列。
简单方法: 一个简单的解决方法是逐个考虑所有子阵列，检查每个子阵列的和。下面的程序实现了简单的解决方案。运行两个循环:外环选择一个起点 I，内环尝试从 I 开始的所有子阵列。 算法:
- 从头到尾遍历数组。
- 从每个索引开始另一个循环，从 i 到数组结束，从 I 开始获取所有子数组，保持一个变量和来计算和。
- 对于内部循环中的每个索引，更新 sum = sum + array[j]
- 如果总和等于给定的总和，则打印子阵列。
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to implement
// the above approach
class SubarraySum
{
/* Returns true if the there is a
subarray of arr[] with a sum equal
to 'sum' otherwise returns false.
Also, prints the result */
int subArraySum(int arr[], int n,
int sum)
{
int curr_sum, i, j;
// Pick a starting point
for (i = 0; i < n; i++)
{
curr_sum = arr[i];
// Try all subarrays starting with 'i'
for (j = i + 1; j <= n; j++)
{
if (curr_sum == sum)
{
int p = j - 1;
System.out.println(
"Sum found between indexes " +
i + " and " + p);
return 1;
}
if (curr_sum > sum || j == n)
break;
curr_sum = curr_sum + arr[j];
}
}
System.out.println("No subarray found");
return 0;
}
// Driver code
public static void main(String[] args)
{
SubarraySum arraysum =
new SubarraySum();
int arr[] = {15, 2, 4, 8,
9, 5, 10, 23 };
int n = arr.length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}
// This code is contributed by Mayank Jaiswal(mayank_24)
输出:
Sum found between indexes 1 and 4
复杂度分析:
- 时间复杂度:最坏情况下的 O(n^2)。 嵌套循环用于遍历数组，因此时间复杂度为 O(n^2)
- 空间复杂度: O(1)。 因为需要恒定的额外空间。
高效方法: 有一个想法，如果数组的所有元素都是正的。如果一个子阵列的总和大于给定的总和，那么向当前子阵列添加元素的总和不可能是 x (给定的总和)。想法是使用类似的方法来滑动窗口。从一个空的子阵列开始，向子阵列添加元素，直到总和小于 x 。如果总和大于 x ，则从当前子阵列的开始处移除元素。 算法:
- 创建三个变量， l=0，sum = 0
- 从头到尾遍历数组。
- 通过添加当前元素更新变量和，和=和+数组[i]
- 如果和大于给定的和，将变量和更新为和=和–数组[l] ，将 l 更新为，l++。
- 如果总和等于给定总和，打印子阵列并中断循环。
Java 语言(一种计算机语言，尤用于创建网站)
// Java program to implement
// the above approach
class SubarraySum
{
/* Returns true if the there is a
subarray of arr[] with sum equal
to 'sum' otherwise returns false.
Also, prints the result */
int subArraySum(int arr[], int n,
int sum)
{
int curr_sum = arr[0], start = 0, i;
// Pick a starting point
for (i = 1; i <= n; i++)
{
// If curr_sum exceeds the sum,
// then remove the starting elements
while (curr_sum > sum && start < i - 1)
{
curr_sum = curr_sum - arr[start];
start++;
}
// If curr_sum becomes equal to sum,
// then return true
if (curr_sum == sum)
{
int p = i - 1;
System.out.println(
"Sum found between indexes " +
start + " and " + p);
return 1;
}
// Add this element to curr_sum
if (i < n)
curr_sum = curr_sum + arr[i];
}
System.out.println("No subarray found");
return 0;
}
// Driver code
public static void main(String[] args)
{
SubarraySum arraysum =
new SubarraySum();
int arr[] = {15, 2, 4, 8,
9, 5, 10, 23};
int n = arr.length;
int sum = 23;
arraysum.subArraySum(arr, n, sum);
}
}
// This code is contributed by Mayank Jaiswal(mayank_24)
输出:
Sum found between indexes 1 and 4
复杂度分析:
- 时间复杂度: O(n)。 只需要遍历一次数组。所以时间复杂度是 O(n)。
- 空间复杂度: O(1)。 因为需要恒定的额外空间。
详情请参考求给定和的子阵|集合 1(非负数)整篇文章！
版权属于：月萌API www.moonapi.com，转载请注明出处
