文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

小易有 n 個(gè)數(shù)字排成一個(gè)環(huán)，你能否將它們分成連續(xù)的兩個(gè)部分(即在環(huán)上必須連續(xù))，使得兩部分的和相等？

輸入描述：

第一行數(shù)據(jù)組數(shù) T ，對(duì)于每組數(shù)據(jù)
第一行數(shù)字 n ，表示數(shù)字個(gè)數(shù)
接下來一行 n 個(gè)數(shù)，按順序給出環(huán)上的數(shù)字。
2 <= n <= 100000, 1 <= Ai <= 10 ^ 9

輸出描述：
對(duì)于每組數(shù)據(jù)，一行輸出YES/NO

示例1: 輸入 1 6 1 2 3 4 5 6 輸出 NO示例2: 輸入 1 4 4 4 5 3 輸出 YES

來源：力扣（LeetCode） 鏈接：https://leetcode-cn.com/problems/S0WXIw
著作權(quán)歸領(lǐng)扣網(wǎng)絡(luò)所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系官方授權(quán)，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處。

2. 解題

#include<bits/stdc++.h> using namespace std; int main() {int T, n, a, i;cin >> T;while(T--){cin >> n; vector<long long> arr(n, 0);//注意溢出i = 0;while(n--){cin >> a;if(i == 0)arr[i] = a;elsearr[i] = arr[i-1] + a;//前綴和i++;}if(arr.back()%2 != 0)//和不能被2整除，分不開{cout << "NO" << endl;continue;}unordered_set<long long> s;long long half = arr.back()/2;bool yes = false;for(i = 0; i < arr.size(); ++i){if(s.count(arr[i]-half)){ //前綴和減去half的值存在，即找到連續(xù)的和為halfyes = true;break;}s.insert(arr[i]);//更新前綴和的集合}if(yes)cout << "YES" << endl;elsecout << "NO" << endl;} }

0 ms 3.2 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長(zhǎng)按或掃碼關(guān)注我的公眾號(hào)（Michael阿明），一起加油、一起學(xué)習(xí)進(jìn)步！

總結(jié)

以上是生活随笔為你收集整理的LeetCode 网易-1. 分割环（前缀和 + 哈希）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。