题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，给你一个整数数组，可以从左或从右一次删除一个数，使得删除的总数之和恰好为x。

思路分享

  • 两个思路，正向和逆向，皆基于不定长滑动窗口(【Leetcode Daily】3090每个字符最多出现两次的最长字符串)。

  • 正向是计算窗口内之和恰好为 x，由于最左和最右的删除形式，可以把原数组拼接。但是还需要限定两点，一个是窗口长度不大于原数组长度；二个是窗口的左侧和右侧满足左侧或者右侧贴边，或者左侧和右侧在加倍窗口的两侧。总之，挺麻烦的。

  • 逆向是，先计算数组之和，目标为最大化窗口内数值，至于删除的结果就拿数组和减去窗口值获得。这个简单，不需要加倍数组，也不需要限定窗口位置。

代码解答（强烈建议自行解答后再看）

  • 正向
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int ans = INT_MAX;
        int m = nums.size();
        //cout << "m:" << m << endl;
        nums.insert(nums.begin(), nums.begin(), nums.end());
        int n = nums.size();
        int cur = 0;        
        int left = 0;
        for (int i = 0; i < n; i++) {
            cur += nums[i];
            while (cur > x) {
                cur -= nums[left++];
            }
            if (cur == x && i-left+1 <= m && (left == 0 || (left <= m && i >= m) || i == n-1)) {
                //cout << left << " " << i << " " << cur << endl;
                ans = min(ans, i-left+1);
            }
        }
        return ans == INT_MAX ? -1 : ans;
    }
};
  • 逆向
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        int win = -1;
        int n = nums.size();
        int target = reduce(nums.begin(), nums.end())-x;
        if (target < 0) return -1;
        int cur = 0;        
        int left = 0;
        for (int i = 0; i < n; i++) {
            cur += nums[i];
            while (target < cur) {
                cur -= nums[left++];
            }
            if (target == cur) {
                win = max(win, i-left+1);
            }
        }
        return win<0 ? -1 : n-win;
    }
};