babula
BAN USERvector<pair<int, int>> find(vector<int> A, int low, int hight) {
vector<pair<int, int>> result;
int n = A.size();
int head = 0;
int tail = 0;
int sum = 0;
while(tail < n){
int temp = sum + A[tail];
if(temp < low){
sum = temp;
tail++;
}else if(temp >=low && temp <=high){
sum = temp;
tail++;
result.push_back(make_pair(head, tail));
}else{
sum -= A[head];
head++;
if(head > tail){
tail = head;
sum = 0;
}
}
}
while(head <= tail){
sum -= A[head];
head++;
if(sum < low){
break;
}else if(sum >= low && sum <=high){
result.push_back(make_pair(head, tail);
}
}
return result;
}
Thanks for checking out my code.
I didn't notice that I need to keep tracking the status of the index array.
Correct the previous solution as below:
void solve(int x[], int xlen, int a[], int alen){
if(xlen != alen || 0 == xlen){
return;
}
sort(x, xlen);
// Add an array b[1 ~ alen] which b[1] = 1, b[2] = 2, ......b[alen] = alen
int b[alen];
for(int i=0; i<alen; i++){
b[i] = i;
}
for(int i=1; i<alen; i++){
// use b array to track the index changing status
if(b[i] != a[i]){
swap(b, a[i], i);
swap(x, a[i], i);
}
}
}
The basic idea is:
1. Sort X.
2. Assume we're going to make 1,2,3,4,......,n sequence become a[1], a[2].......a[n]. we swap x[] as we swap a[]. For example, if a[1] = 3, we swap 1 and 3 to make 3 at a[1]. At the same time, we swap x[1] with x[3] and so on.
void solve(int x[], int xlen, int a[], int alen){
if(xlen != alen || 0 == xlen){
return;
}
sort(x, xlen);
for(int i=1; i<alen; i++){
if(a[i] != i){
swap(x, a[i], i);
}
}
}
void swap(int array[], int a, int b)
{
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
void sort(int array[], int arrayLength)
{
//some sort implementation
}
It's really a good answer.
- babula April 24, 2014However, since you want to solve negative input at the same time, you might want to handle the solution when S < 0 ?
For example, S= -5, array is {-1}, the result should be 1.
I guess that is asking too much :P