题目浅析

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

  • 简单地说，就是给一个数组，可以将该数组无限地复制自身，求无限的数组中，子数组和恰好为 target 的最短长度。

思路分享

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

  • 参考解法
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 minSizeSubarray(vector<int>& nums, int target) {
        long long all_sum = reduce(nums.begin(), nums.end(), 0LL);
        int target_sum = target % all_sum;
        int left = 0;
        int ans = INT_MAX;
        long long cur_sum = 0;
        int n = nums.size();
        for (int right = 0; right < 2*n; right++) {
            cur_sum += nums[right%n];
            while(cur_sum > target_sum) {
                
                cur_sum -= nums[left++%n];
            }
            if (cur_sum == target_sum) {
                //cout << "cur:" << cur_sum << "; nums[left]:" << nums[left] << "; left:" << left << "; right:" << right << endl;
                ans = min(ans, right-left+1);
            }
        }
        return ans == INT_MAX ? -1 : ans  + target / all_sum * n;
    }
};