产生一个给定的和与积子阵列 [英] Sub array that produces a given sum and product

问题描述

由于长度为N，你会怎么找到的最小长度的数组 邻接子阵列的，其总和是S和其产物是P. 对于如 5 6 1 4 6 2 9 7 为S = 17，答案= [6,2，9] 为P = 24，答案= [4〜6] 。

Given an array of length N. How will you find the minimum length contiguous sub-array of whose sum is S and whose product is P. For eg 5 6 1 4 6 2 9 7 for S = 17, Ans = [6, 2, 9] for P = 24, Ans = [4 6].

推荐答案

刚刚从左至右去，总结所有的数字，如果和> S，然后扔掉离开的。

Just go from left to right, and sum all the numbers, if the sum > S, then throw away left ones.

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)));
        }
    }
}

---

有关你的榜样，我觉得是的或的。

产品的是从没有的的不同之的，除了计算。

Product is nothing different from sum, except for calculation.

这篇关于产生一个给定的和与积子阵列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！