i*********7
发帖数: 348 | 1 given an array of integers(positive or negative), and two integers x, y.
write a function that can find a subarray whose sum equals to x and product
equals to y
这题还有另一个变种：
Given an array with n positive and negative numbers, find the subarray with
one or more
consecutive numbers where the sum of the subarray is maximum.
看看大家有么有思路。。 |
l*********8
发帖数: 4642 | 2 sub-array 是要连续的吧？
product
with
【在 i*********7 的大作中提到】
: given an array of integers(positive or negative), and two integers x, y.
: write a function that can find a subarray whose sum equals to x and product
: equals to y
: 这题还有另一个变种：
: Given an array with n positive and negative numbers, find the subarray with
: one or more
: consecutive numbers where the sum of the subarray is maximum.
: 看看大家有么有思路。。
|
i*********7
发帖数: 348 | 3 对，要连续的
【在 l*********8 的大作中提到】
: sub-array 是要连续的吧？
:
: product
: with
|
w****x
发帖数: 2483 | 4 分配一个sum[n]: sum[i] = a[0] + a[1] + ... + a[i]
分配一个mul[n]: mul[i] = a[0]*a[1]...*a[i]
求i, j j > i 且 sum[j]-sum[i] == x && mul[j]/mul[i] == y
没考虑溢出. 要考虑的话用字符串乘除代替?? |
w****o
发帖数: 2260 | 5 有两个疑问：
1. 你的题目中的 x, y是任意给的吗？很有可能 和是x, 乘积是y的subarray根本不存
在，对吧？！
2. 你说的那个变形题不就是著名的max sum subarray的题吗？难道有什么特别的吗？
不是有O(n)的算法吗？
谢谢！
product
with
【在 i*********7 的大作中提到】
: given an array of integers(positive or negative), and two integers x, y.
: write a function that can find a subarray whose sum equals to x and product
: equals to y
: 这题还有另一个变种：
: Given an array with n positive and negative numbers, find the subarray with
: one or more
: consecutive numbers where the sum of the subarray is maximum.
: 看看大家有么有思路。。
|
c****p
发帖数: 6474 | 6 这两题不一样吧，，，后者是经典DP
product
with
【在 i*********7 的大作中提到】
: given an array of integers(positive or negative), and two integers x, y.
: write a function that can find a subarray whose sum equals to x and product
: equals to y
: 这题还有另一个变种：
: Given an array with n positive and negative numbers, find the subarray with
: one or more
: consecutive numbers where the sum of the subarray is maximum.
: 看看大家有么有思路。。
|
c****p
发帖数: 6474 | |
f**********2
发帖数: 2401 | 8 如果subarray是指的位置连续的integer，正解。其实就是遍历所有可能，brute force？
【在 w****x 的大作中提到】
: 分配一个sum[n]: sum[i] = a[0] + a[1] + ... + a[i]
: 分配一个mul[n]: mul[i] = a[0]*a[1]...*a[i]
: 求i, j j > i 且 sum[j]-sum[i] == x && mul[j]/mul[i] == y
: 没考虑溢出. 要考虑的话用字符串乘除代替??
|
f**********2
发帖数: 2401 | 9 满足要求的不存在，就输出－1,退出。
就是max sum subarray，agree
【在 w****o 的大作中提到】
: 有两个疑问：
: 1. 你的题目中的 x, y是任意给的吗？很有可能 和是x, 乘积是y的subarray根本不存
: 在，对吧？！
: 2. 你说的那个变形题不就是著名的max sum subarray的题吗？难道有什么特别的吗？
: 不是有O(n)的算法吗？
: 谢谢！
:
: product
: with
|
l*********8
发帖数: 4642 | 10 先找sum等于给定数字的sub-array, 然后检查这个sub-array的product是否满足要求。
下面算法找sum等于给定数字的sub-array
input:
int a[]; // array
int n; // array size
Step 1, sort the input array a[] O(nlogn)
Step 2, 找到a[]中的第一个正数, 记下标为 indexP;
Step 3, 在 a[0 ... indexP-1] (负数和零部分）中寻找sum等于给定数字的sub-array
O(n)
Step 4，在 a[indexP ... n-1] (正数部分）中寻找sum等于给定数字的sub-array O
(n)
Step 5, 在 整个a[] 中寻找sum等于给定数字的sub-array, 但是限定sub_array开始于
负数部分，结束于正数部分。 O(n)
检查sub_array 的product是否满足要求， O(l), where l is the length of the sub
-array. 因为sub-array的长度跟n是一个数量级的，所以O(l) = O(n).
对每一个满足sum条件的sub-array, 都要检查product是否满足要求。 综合起来， 算
法复杂度是O(n^2).
product
with
【在 i*********7 的大作中提到】
: given an array of integers(positive or negative), and two integers x, y.
: write a function that can find a subarray whose sum equals to x and product
: equals to y
: 这题还有另一个变种：
: Given an array with n positive and negative numbers, find the subarray with
: one or more
: consecutive numbers where the sum of the subarray is maximum.
: 看看大家有么有思路。。
|
|
|
l*********8
发帖数: 4642 | 11 如果题目只要求返回一个sub-array， 那么找到这样的sub-array后，程序就可以结束。
另外，一些简单的检查也可以避免无用的查找。
比如： 如果要求的product为负，则不用step 4; 如果要求的sum为正，则不需要step
3. 如果要求的product为正，则在step3里面的sub-array size总是要偶数等等
array
O
【在 l*********8 的大作中提到】
: 先找sum等于给定数字的sub-array, 然后检查这个sub-array的product是否满足要求。
: 下面算法找sum等于给定数字的sub-array
: input:
: int a[]; // array
: int n; // array size
: Step 1, sort the input array a[] O(nlogn)
: Step 2, 找到a[]中的第一个正数, 记下标为 indexP;
: Step 3, 在 a[0 ... indexP-1] (负数和零部分）中寻找sum等于给定数字的sub-array
: O(n)
: Step 4，在 a[indexP ... n-1] (正数部分）中寻找sum等于给定数字的sub-array O
|
J***e
发帖数: 50 | 12 If there is a 0 in the array, will this multiplication still work?
【在 w****x 的大作中提到】
: 分配一个sum[n]: sum[i] = a[0] + a[1] + ... + a[i]
: 分配一个mul[n]: mul[i] = a[0]*a[1]...*a[i]
: 求i, j j > i 且 sum[j]-sum[i] == x && mul[j]/mul[i] == y
: 没考虑溢出. 要考虑的话用字符串乘除代替??
|
m*****g
发帖数: 226 | |
p*****2
发帖数: 21240 | 14
brute force感觉要O(n^3)
这题如果能达到n^2应该就是最佳答案了吧？
【在 m*****g 的大作中提到】
: brute force, O(n^2)
|
m*****k
发帖数: 18 | 15 编了一下O(n)的maximum subarray问题：
int maxSubArray(int A[], int n) {
int max = A[0], max_neg = A[0], sum = 0;
bool flag = false; // test all negtive integers
for (int i = 0 ; i < n; i++)
{
if (A[i] >= 0)
flag = true;
else if (A[i] > max_neg)
max_neg = A[i];
sum += A[i];
if (sum < 0)
sum = 0;
else if (sum > max)
max = sum;
}
return flag?max:max_neg;
}
leetcode上测试通过 |
