给定一个长度为N的数组。您将如何找到其和为S且乘积为P的最小长度连续子数组5 6 1 4 6 2 9 7 for S = 17, Ans = [6, 2, 9] for P = 24, Ans = [4 6]。
5 6 1 4 6 2 9 7
for S = 17, Ans = [6, 2, 9]
for P = 24, Ans = [4 6]
只需从左到右,对所有数字求和,如果总和> S,则丢弃左数。
import java.util.Arrays; public class test { public static void main (String[] args) { int[] array = {5, 6, 1, 4, 6, 2, 9, 7}; int length = array.length; int S = 17; int sum = 0; // current sum of sub array, assume all positive int start = 0; // current start of sub array int minLength = array.length + 1; // length of minimum sub array found int minStart = 0; // start of of minimum sub array found for (int index = 0; index < length; index++) { sum = sum + array[index]; // Find by add to right if (sum == S && index - start + 1 < minLength) { minLength = index - start + 1; minStart = start; } while (sum >= S) { sum = sum - array[start]; start++; // Find by minus from left if (sum == S && index - start + 1 < minLength) { minLength = index - start + 1; minStart = start; } } } // Found if (minLength != length + 1) { System.out.println(Arrays.toString(Arrays.copyOfRange(array, minStart, minStart + minLength))); } } }
对于您的示例,我认为它是 OR 。
__除计算外, 积 与 和 没有什么不同。