遇到一个测试题,有没有大佬能够帮忙优化解决呀?
//爱德华有1个包含N个整数的数组A,他定义1个数组的美丽值为数组中所有不同整数的和。现在爱德华想知道数组A的所有连续子序列的美丽值之和。 //楼主很笨,用了一个很傻的方法,每次都遍历一遍,时间复杂度都达到O(N^4)了,能不能帮助楼主想个好办法呢? //测试用例: //1, 1, 2 => 11 //1, 2 => 6 //1,2,3,3 => 37package 测试;
public class Test1 {
public static void main(String[] args) {
int arr[] = { 1,1,3,3 };
System.out.println(beauty_of_array(arr));
}
/*
* 实现代码:Java
* 该函数用于计算数组中所有连续子序列的美丽值之和
*/
private static int beauty_of_array(int[] array) {
// 数组的长度
int length = array.length;
// 如果输入的数组不合法,返回0,表示没有美丽值
if (array == null || length <= 0)
return 0;
// 用于统计美丽值的总和
int beautyValue = 0;
// 统计所有可能存在的子序列的和
while (length > 0) {
beautyValue = beauty_of_array(array, length);
length--;
}
return beautyValue;
}
/*
* 该函数用于统计连续的n个数作为一个子序列可得到的美丽值之和
*/
private static int beauty_of_array(int array[], int count) {
// 如果已经把所有的子串都统计完毕,则不用再进行递归,返回0退出
if (count <= 0)
return 0;
// 用于记录美丽值
int beautyValue = 0;
// 用于存放数组的长度
int length = array.length;
// 用于储存子串的数量
int num = length - count 1;
// 循环时的计数器
int i = 0, j = 0, k = 1;
// 用于记录当前子串是否存在相同的其他子串
boolean exsist = false;
// 计算子序列个数为count的所有不重复子序列的和
for (i = 0; i < num; i ) {
exsist=false;
// 检查数组中是否存在相同的子串
for (j = 0; j < num; j ) {
k = 0;
if (array[j] == array[i] && j != i) {
k = 1;
while (k < count && array[j k] == array[i k])
k ;
}
//如果存在一个相同的子序列,令exsisit为空,跳出检查循环进行下一个子序列的判断
if (k == count) {
exsist = true;
break;
}
}
// 如果子串并没有出现过,则相加
if (!exsist) {
beautyValue = getBeautyValue(array, count, i);
}
}
return beautyValue;
}
/*
* 获取下标从startPos开始往后count个数字的和
* */
private static int getBeautyValue(int[] array, int count, int startPos) {
int value=0;
for(int i=startPos;i<startPos count;i )
value =array[i];
return value;
}
}
#测试#