穷举法的时间复杂度为 O(nm - m^2), 略去实现.
以下实现的时间复杂度为 O(n - m), 空间复杂度为 O(1).
public class Test {
public static void main(String[] args) {
int[] numberArr = {1, 2, 4, 6, 2, 1, 0, -1, 8, 10, 0};
int range = 4;
int result = find(numberArr, range);
System.out.println("满足条件的子集的起始索引为: " + result);
}
public static int find(int[] numberArr, int range) {
int target = 0, i = 0, j = range;
int isum = 0, jsum = 0;
for (; j < numberArr.length; i++, j++) {
isum += numberArr[i];
jsum += numberArr[j];
if (isum < jsum) {
target = j + 1 - range;
isum = 0;
jsum = 0;
}
}
return target;
}
}
