資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告