用java编程：输入一个集合,可以有正数有负数,写一个程序 输出集合内所有数值的和最小的连续子集有一组数

发布网友 发布时间：2022-05-12 07:20

我来回答

共3个回答

热心网友 时间：2024-02-19 13:27

package com.arc.test;

public class MiniArrayTest {


public static void main(String[] args) {
int[] arr = {-15, 3, 3, -20, 1, -4};
getMiniArray(arr);
}

public static void getMiniArray(int[] arr){

int startIndex = 0;
int endIndex = 0;
int temp = Integer.MAX_VALUE;
int min = 0;

// 如果数组长度为1或2，则最小的连续子集就是自己
if(arr.length <= 2){
for(int i = 0; i < arr.length; i++){
System.out.println(arr[i] + ",");
}
return;
}

// 用index标注出现负数的数组下标，依次比较结果，index将停留在数值最小的地方
// 此时，时间复杂度是O(n)
for(int i = 0; i < arr.length; i++){
if(arr[i] < 0){
min += arr[i];
if(min <= temp){
startIndex = endIndex;
endIndex = i;
temp = min;
min = arr[endIndex];
}
}else{
min += arr[i];
}
}

// 如果endIndex > 0，说明数组中有负数，则把startIndex和endIndex之前的元素打印出来
// 这里，最大时间复杂度(n)
// 所以，总的时间复杂度2O(n)，也可以当作O(n)
if(endIndex > 0){
if(startIndex == 0){
for(int i = startIndex; i <= endIndex; i++){
System.out.print(arr[i] + ",");
}
}
// 如果endIndex = 0，说明数组中没有负数，则把连续的最小的两个整数输出，就是最小连续子集合
// 这里，最大时间复杂度(n)
// 所以，总的时间复杂度2O(n)，也可以当作O(n)
}else{
endIndex = 1;
min = arr[0] + arr[1];
for(int i = 2; i < arr.length; i++){
if(arr[i - 1] + arr[i] <= min){
min = arr[i] + arr[i - 1];
endIndex = i - 1;
}
}
System.out.println(arr[endIndex - 1] + "," + arr[endIndex]);
}
}
}

追问非常感谢你的回答，虽然在你设置的数组实验时 答案是正确的 但是 我认为28行起到40行

有些逻辑错误，因为当我置换数组为arr【-1,3,3,-2,1,-4】时 程序就有错误，而且temp 就失去其意义。
恳请您再费些脑力为我解答。非常感谢。

追答嗯，谢谢提醒。写的比较着急所以不太严谨。但是我想你应该明白我的思路了。你可以自己试试，我想这样才会有进步哦~

热心网友 时间：2024-02-19 13:28

不可能的！追问能否告诉我为什么不可能 ，有什么逻辑矛盾吗

追答逻辑矛盾是没有的，只不过要求O(N)谁也设计不出来

热心网友 时间：2024-02-19 13:28

我不知道，应该是不可能的！