提问人：physicsuser 提问时间：11/15/2023 最后编辑：Mark Rotteveelphysicsuser 更新时间：11/15/2023 访问量：84
如何将 O（n^2） 简化为 O（n） 复杂度？[关闭]
How to reduce O(n^2) to O(n) complexity? [closed]
问：
给定一个大小为 N 且仅包含正值的未排序数组 A 整数，找到一个连续的子数组，该子数组与给定的数字 S 相加 并返回其左右索引（从 1 开始的索引） 子阵列。
如果有多个子数组，则返回子数组索引，这些索引来自 首先从左向右移动。
注意：您必须返回一个由两个元素组成的 ArrayList 和对。如果不存在这样的子数组，则返回一个包含 元素 -1。
static ArrayList<Integer> subarraySum(int[] arr, int n, int s)
{
// Your code here
for (int i =0 ; i < n; i++){
int acc = 0;
for ( int j =i;j < n; j++ ){
acc += arr[j];
if(acc == s){
return new ArrayList<>(Arrays.asList(i+1,j+1));
}
if(acc > s){
break;
}
}
}
return new ArrayList<>(Arrays.asList(-1));
}
我有这个代码。谁能帮我降低它的时间复杂性？
答：
0赞
Mayfair
11/15/2023
#1
这应该可以帮助您入门。
static ArrayList<Integer> subarraySum(int[] arr, int n, int s) {
int start = 0;
int end = 0;
int currentSum = 0;
while (end < n || currentSum > s) {
if (currentSum == s) {
return new ArrayList<>(Arrays.asList(start + 1, end));
} else if (currentSum < s) {
currentSum += arr[end];
end++;
} else {
currentSum -= arr[start];
start++;
}
}
return new ArrayList<>(Arrays.asList(-1));
}
评论