数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Java 中不同方法求解给定和的子数组
查找给定和的子数组是一个常见问题，经常出现在编码面试和编程竞赛中。这个问题可以使用多种技术来解决，每种技术在时间复杂度和空间复杂度方面都有自己的权衡。在本文中，我们将探讨多种方法来解决在Java中查找给定和的子数组的问题。
问题陈述
给定一个数组和目标和，找到数组中一个连续的子数组，使其元素之和等于给定的目标和。这个问题可以分为两个主要变体
- 仅包含正数的子数组：数组仅包含正数。
- 包含正负数的子数组：数组包含正数和负数。
让我们探索不同的方法来解决这些变体。
方法 1：使用暴力法
暴力法涉及检查所有可能的子数组并计算它们的和，以查看其中是否有任何一个等于目标和。这种方法适用于两种变体，但对于大型数组效率低下，因为它具有二次时间复杂度。
实现
public class SubarraySumBruteForce {
public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
int n = arr.length;
for (int start = 0; start < n; start++) {
int currentSum = 0;
for (int end = start; end < n; end++) {
currentSum += arr[end];
if (currentSum == targetSum) {
return new int[] {
start,
end
};
}
}
}
return new int[] {
-1, -1
}; // Return -1 if no subarray is found
}
public static void main(String[] args) {
int[] arr = {
1,
2,
3,
7,
5
};
int targetSum = 12;
int[] result = findSubarrayWithGivenSum(arr, targetSum);
if (result[0] != -1) {
System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
} else {
System.out.println("No subarray with given sum found.");
}
}
}
输出
Subarray found from index 1 to 3
分析
- 时间复杂度：由于两个嵌套循环遍历数组，因此为 O(n²) 。
- 空间复杂度：O(1)，因为除了输入数组之外没有使用其他空间。
方法 2：使用滑动窗口
滑动窗口方法对于仅包含正数的数组是有效的。此技术涉及维护一个元素窗口，这些元素加起来等于目标和。通过添加元素扩展窗口，直到总和超过目标，然后通过从开头删除元素收缩窗口，直到总和小于或等于目标。
实现
public class SubarraySumSlidingWindow {
public static int[] findSubarrayWithGivenSum(int[] arr, int targetSum) {
int start = 0;
int currentSum = 0;
for (int end = 0; end < arr.length; end++) {
currentSum += arr[end];
while (currentSum > targetSum && start < end) {
currentSum -= arr[start];
start++;
}
if (currentSum == targetSum) {
return new int[] {
start,
end
};
}
}
return new int[] {
-1, -1
}; // Return -1 if no subarray is found
}
public static void main(String[] args) {
int[] arr = {
1,
2,
3,
7,
5
};
int targetSum = 12;
int[] result = findSubarrayWithGivenSum(arr, targetSum);
if (result[0] != -1) {
System.out.println("Subarray found from index " + result[0] + " to " + result[1]);
} else {
System.out.println("No subarray with given sum found.");
}
}
}
输出
Subarray found from index 1 to 3
分析
- 时间复杂度：O(n)，因为每个元素最多处理两次。
- 空间复杂度：O(1)，因为不需要额外的空间。
更新于： 2024年8月14日
86 次查看
广告