c++ PS Find pivot Index, Find minimum subarray with O(n)

Brute force를 사용하면 쉽게 해결할 수 있으나

O(n)으로 해결하도록 하자.

코드 >>

#include <iostream>
#include <vector>
#include <numeric>
 
// 문제 1.Find Pivot Index
// [1,8,2,9,2,3,6] (1+8+2 == 2+3+6) 9가 Pivot!
// [2,5,7] 피봇이 없음 -> -1 Return하기
// O(n)에 계산할 수 있다.
 
// 문제 2. minimum sub array 찾기
 
int pivotIndex(std::vector<int>& nums)
{
    int sum = std::accumulate(nums.begin(), nums.end(), 0);
    int leftSum = 0;
    int rightSum = 0;
    int pivot = 0;
    int pastPivotNum = 0;
    for (auto idx = 0; idx < nums.size(); idx++)
    {
        pivot = nums[idx];
        
        leftSum = pastPivotNum + leftSum;
        rightSum = sum - pivot - leftSum;
 
        if (leftSum == rightSum)
            return idx;
 
        pastPivotNum = pivot;
    }
    return -1;
}
 
//Given an array of positive integers nums and a positive integer
//target, return the minimal length of a contiguous subarray
//[numsl, numsl+1, ..., numsr-1, numsr] of which the sum is greater
//than or equal to target. If there is no such subarray, return 0
//instead.
int minimum_subarray(std::vector<int>& nums, int target)
{
    int sum = 0;
    int ans = INT_MAX;
    int left = 0;
    for (auto idx = 0; idx < nums.size(); idx++)
    {
        sum += nums[idx];
        while (sum >= target)
        {
            ans = std::min(ans, idx + 1 - left);
            sum -= nums[left++];
        }
 
 
    }
    return (ans != INT_MAX) ? ans : 0;
}
 
int main()
{
    // Find Pivot Index
    std::vector<int> nums = { 1, 8, 2, 9, 2, 3, 6 };
    //std::vector<int> nums = { 1,2,7};
    std::cout << pivotIndex(nums) << std::endl;
 
    // Find minimum Size Subarray Sum
    std::vector<int> nums1 = { 2,3,1,2,4,3 };
    std::cout << minimum_subarray(nums1, 7) << std::endl;
 
    return 0;
}