终于有人做pearl，给一个我的解答
此题是第9题的扩展，第9题求的是subvector whose sum is close to zero,解答如下
(python)
def Subvector_Zero(v):
"find the subvector whose sum is close to zero"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(1,len(v)):
minv=min(minv,s[i]-s[i-1])
return minv
C++:
/*Description: find the subvector whose sum is close to zero
Input: vector t
Output: int
K.O.: auxiliary sum array
*/
int Pearl::Vector_zero(vector t){
int n=t.size();
vector sum(n,0);
sum[0]=t[0];
for(int i=1;isum[i]=t[i]+sum[i-1];
sort(sum.begin(),sum.end());
int minv=numeric_limits::max();
for(int i=1;iminv=min(minv,sum[i]-sum[i-1]);
return minv;
}
于是要求sum 为k, 就是在sum array中排序后进行binary search找离他距离为k的j，
然后比较找出最小值，即可，有点麻烦，不过还好
def BS_range(v,x):
"find x within v if found return index otherwise return the index\
of its closest value"
l,r=0,len(v)-1
if x<=v[l]: return l
if x>=v[r]: return r
while l<=r:
mid=l+(r-l)//2
if v[mid]<=x and x<=v[mid+1]: return mid+1
elif v[mid+1]else:r=mid
def Subvector_k(v,k):
"find the subvector whose sum is k"
s=[0 for a in range(len(v))]
s[0]=v[0]
for i in range(1,len(v)):
s[i]=v[i]+s[i-1]
s=sorted(s)
minv=sys.maxint
for i in range(len(v)):
j=BS_range(s,s[i]+k)
jj=(j==len(v)-1) and j or j+1
minv=min(minv,abs(s[j]-s[i]-k))
minv=min(minv,abs(s[jj]-s[i]-k))
return minv+k
C++:
/*Description: given an sorted array, if a value is in it, return its index;
otherwise return
the index of closest value
Input: vector t, int x
Output: int
K.O.: Binary Search Variant
*/
int Pearl::BS_range(vector t, int x){
int l=0,r=t.size()-1;
if(x<=t[l]) return l;
if(x>=t[r]) return r;
while(l<=r){
int mid=l+(r-l)/2;
if(t[mid]<=x&&x<=t[mid+1]) return mid+1;
else if(t[mid+1]else r=mid;
}
return -1;
}
/*Description: find the subvector whose sum is close to K
Input: vector t, int x
Output:int
K.O.: similar to vector_zero but with BS_range*/
int Pearl::Subvector_k(vector t, int x){
int n=t.size();
vector sum(n,0);
sum[0]=t[0];
for(int i=1;isum[i]=t[i]+sum[i-1];
sort(sum.begin(),sum.end());
int minv=numeric_limits::max();
for(int i=0;iint j=BS_range(sum,sum[i]+x);
int jj=(jminv=min(minv,abs(sum[j]-sum[i]-x));
minv=min(minv,abs(sum[jj]-sum[i]-x));
}
return abs(minv-x);
}
