程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> 區間和問題——九度 1554

區間和問題——九度 1554

編輯：關於C++

題目描述：

給定一個數組，判斷數組內是否存在一個連續區間，使其和恰好等於給定整數k。

輸入：

輸入包含多組測試用例，每組測試用例由一個整數n(1<=n<=10000)開頭，代表數組的大小。
接下去一行為n個整數，描述這個數組，整數絕對值不大於100。
最後一行為一個整數k(大小在int范圍內)。

輸出：

對於每組測試用例，若存在這個連續區間，輸出其開始和結束的位置，s，e(s <= e)。
若存在多個符合條件的輸出，則輸出s較小的那個，若仍然存在多個，輸出e較小的那個。
若不存在，直接輸出No。

樣例輸入：

5
-1 2 3 -4 9
5
3
-1 2 -3
7
2
-1 1
0

樣例輸出：

2 3
No
1 2

思路：sum[i] 表示前i項和，題意即變為求是否存在 sum[i] - sum[j-1] == k，直接枚舉無法通過。把式子轉化一下可變為：sum[i] == sum[j-1] + k；題意又變為求是否存在一個sum[i] 使sum[j-1] + k == sum[i] 成立。這樣直接過一遍就可以了。在不考慮前綴和相同的情況，用map標記就可以完成查找工作，如果存在前綴和相同的情況，用個vector容器跟每個前綴和對應就可以了。

#include 
#include 
#include 
#include
#include 
#define M 10010
#define OFFSET 1000000
#define MIN(x, y) ((x) < (y) ? (x) : (y))
int sum[M];
using namespace std;
vectorcnt[M];
 
int main()
{
    //freopen(in.txt, r, stdin);
    int n;
    int i, j, k, a, t, s, u;
    while(~scanf(%d, &n))
    {
        u = 1;
        mapvis;
        memset(sum, 0, sizeof(sum));
        for(i=0; i OFFSET){
            printf(No
);
            continue;
        }
        int left = 0, right = 0;
        int flag = 0;
        for(i=1; i<=n; i++){
            t = sum[i-1] + k;
            if(vis[t]){
                int b = vis[t];
                for(j=0; j= i){
                        flag = 1;
                        left = i;
                        right = cnt[b][j];
                        break;
                    }
                }
                if(flag) break;
            }
        }
        if(flag) printf(%d %d
, left, right);
        else printf(No
);
        for(i=0; i