Day 47 Number of Operations to Decrement Target to Zero

Number of Operations to Decrement Target to Zero

题目

You are given a list of positive integers nums and an integer target.

Consider an operation where we remove a number v from either the front 

or the back of nums and decrement target by v.

Return the minimum number of operations required to decrement target to zero. 

If it's not possible, return -1.

Constraints

n ≤ 100,000 where n is the length of nums
Example 1
Input
nums = [3, 1, 1, 2, 5, 1, 1]
target = 7
Output
3
Explanation
We can remove 1, 1 and 5 from the back to decrement target to zero.

Example 2
Input
nums = [2, 4]
target = 7
Output
-1
Explanation
There's no way to decrement target = 7 to zero.

题目思路

• 1、滑动窗口题目，数组遍历一次求和，刚好相等则不用减。
• 2、不相等则减去目标值，即为最少需要去除的值，使用双指针滑动，如果大于去除值，则左指针向前滑动，相等则对比之前操作的长度，记录其中最大的移动长度，即为最小的移动区间。

int solve(vector<int>& nums, int target) {
    int n = nums.size();
    int sum;

    for(int i = 0; i < n; i++)
    {
        sum += nums[i];
    }
    if (sum == target) return n;
	sum -= target;

    int l = 0, total = 0, pos = 0;
    for (int r = 0; r < n; r++)
    {
        total += nums[r];
        while(total > sum)
        {
            total -= nums[l++];
        }
        if (total == sum)
        {
            pos = max(pos, r - l + 1);
        }
    }
    return pos > 0 ? n - pos : -1;
}

复杂度

• 时间复杂度：O(n)

• 空间复杂度：O(1)