[LeetCode] 2270. Number of Ways to Split Array

https://leetcode.com/problems/number-of-ways-to-split-array/description/

leetcode - Number of Ways to Split Array

문제 유형: 슬라이딩 윈도우, 구간합

문제 난이도: Medium

 

문제

You are given a 0-indexed integer array nums of length n.

nums contains a valid split at index i if the following are true:

• The sum of the first i + 1 elements is greater than or equal to the sum of the last n - i - 1 elements.
• There is at least one element to the right of i. That is, 0 <= i < n - 1.

Return the number of valid splits in nums.

 

0-Indexed의 정수 배열 nums가 주어진다. 길이는 n이다.

 

첫 i+1개의 요소들의 합이 마지막 n-i-1개의 합보다 크면, 유효한 스플릿이다.

단, 0 <= i < n-1이다.

유효한 스플릿의 개수를 구하시오.

 

풀이

우선 처음에 배열을 순차적으로 읽으면서 오른쪽 부분에 모두 누적한다.

그 뒤, 배열을 0 ~ n-2까지 순회하면서 순차적으로 오른쪽부분에 숫자를 빼고 왼쪽부분에 숫자를 더한다.

 

만약 그 과정에서 l > r이라면, 개수를 1 추가한다.

최종 개수를 반환한다.

 

코드

C++

#pragma GCC optimize("O3", "unroll-lops");
static const int __ = [](){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    return 0;
}();

class Solution {
public:
    int waysToSplitArray(vector<int>& nums) {
        long long l = 0, r = 0;
        int n = nums.size();
        int ans = 0;
        for(int i = 0; i < n; ++i) {
            r += nums[i];
        }

        for(int i = 0; i < n-1; ++i) {
            l += nums[i];
            r -= nums[i];
            if(l >= r) ans++;
        }

        return ans;
    }
};