- 题目描述：
-
给定一个数组，判断数组内是否存在一个连续区间，使其和恰好等于给定整数k。
- 输入：
-
输入包含多组测试用例，每组测试用例由一个整数n(1<=n<=10000)开头，代表数组的大小。
接下去一行为n个整数，描述这个数组，整数绝对值不大于100。最后一行为一个整数k(大小在int范围内)。
- 输出：
-
对于每组测试用例，若存在这个连续区间，输出其开始和结束的位置，s，e(s <= e)。
若存在多个符合条件的输出，则输出s较小的那个，若仍然存在多个，输出e较小的那个。若不存在，直接输出"No"。
- 样例输入：
-
5-1 2 3 -4 953-1 2 -372-1 10
- 样例输出：
-
2 3No1 2
思路
1. o(n^n) 复杂度算法超时
2. 正解. D[i] 记录 0~i 的和, 若 D[j] - D[i] == k, 那么 i~j 是一个可行解. 对 D[i] 进行索引排序后枚举 i 并使用二分查找 j. 时间复杂度为 o(nlogn)
代码 未通过九度测试
#include#include #include using namespace std;class Node {public: int i, di; Node(int _i, int _di):i(_i), di(_di) { } Node() { Node(0, 0); } bool operator<(const Node &ths) const { if(this->di == ths.di) return this->i < ths.i; return this->di < ths.di; }};int d[10010];int arr[10010];Node nodes[10010];int st, ed;int binary_search(int low, int high, int target, int &left, int &right) { int low1 = low, high1 = high; // find the left part of array while(low1 <= high1) { int mid = (low1+high1)>>1; if(nodes[mid].di < target) { low1 = mid + 1; }else{ high1 = mid -1; } } left = low1; low1 = low, high1 = high; while(low1 <= high1) { int mid = (low1+high1)>>1; if(nodes[mid].di <= target) { low1 = mid + 1; }else{ high1 = mid -1; } } right = high1; if(left < low || right > high || nodes[left].di != target) return -1; return 0;}int main() { freopen("testcase.txt", "r", stdin); int n, k; while(scanf("%d", &n) != EOF) { scanf("%d", arr); nodes[0].i = 0; nodes[0].di = arr[0]; d[0] = arr[0]; for(int i = 1; i < n; i ++) { scanf("%d", arr+i); d[i] = d[i-1]+arr[i]; nodes[i].i = i; nodes[i].di = d[i]; } scanf("%d", &k); sort(nodes, nodes+n); int minst = 0, mined = 0x3f3f3f3f; for(int i = 0; i < n; i ++) { int target; if(i == 0) { target = k; }else{ target = d[i-1] + k; } int left, right; if(binary_search(0, n-1, target, left, right) == -1) { // didn't find continue; }else { for(int j = left; j <= right; j ++) { int index = nodes[j].i; if(index < i) continue; minst = i; mined = index; break; } break; } } if(mined != 0x3f3f3f3f) printf("%d %d\n",minst+1, mined+1 ); else printf("No\n"); } return 0;}