ケータイで書いてたら意味不明になってしまった。
間違ってなかったらO(n^2/2)位かな？

void search(int* a, int ln, int t, int startEnd[2]) {
int m, n, M, N;
int unko;
startEnd[0]=startEnd[0]=-1;
for(M=0, N=ln; M < N;) {
int sum;
for(m=M, sum=0; m < N; m++) {
int sAbs;
sum+=a[m];
if(unko > abs((sAbs = (sum - t)))) {
unko = sAbs;
startEnd[0]=M; startEnd[1]=m;
}}
N--;
for(n=N, sum=0; n > M; n--) {
int sAbs;
sum+=a[n];
if(unko > abs((sAbs = (sum - t)))) {
unko = sAbs;
startEnd[0]=N; startEnd[1]=n;
}}
M++;
if(unko == t) break;}}