Question

2875. 无限数组的最短子数组

English Version

题目描述

给你一个下标从 0 开始的数组 nums 和一个整数 target 。

下标从 0 开始的数组 infinite_nums 是通过无限地将 nums 的元素追加到自己之后生成的。

请你从 infinite_nums 中找出满足 元素和 等于 target 的 最短 子数组，并返回该子数组的长度。如果不存在满足条件的子数组，返回 -1 。

 

示例 1：

输入：nums = [1,2,3], target = 5
输出：2
解释：在这个例子中 infinite_nums = [1,2,3,1,2,3,1,2,...] 。
区间 [1,2] 内的子数组的元素和等于 target = 5 ，且长度 length = 2 。
可以证明，当元素和等于目标值 target = 5 时，2 是子数组的最短长度。

示例 2：

输入：nums = [1,1,1,2,3], target = 4
输出：2
解释：在这个例子中 infinite_nums = [1,1,1,2,3,1,1,1,2,3,1,1,...].
区间 [4,5] 内的子数组的元素和等于 target = 4 ，且长度 length = 2 。
可以证明，当元素和等于目标值 target = 4 时，2 是子数组的最短长度。

示例 3：

输入：nums = [2,4,6,8], target = 3
输出：-1
解释：在这个例子中 infinite_nums = [2,4,6,8,2,4,6,8,...] 。
可以证明，不存在元素和等于目标值 target = 3 的子数组。

 

提示：

• 1 <= nums.length <= 105
• 1 <= nums[i] <= 105
• 1 <= target <= 109

解法

方法一：前缀和 + 哈希表

我们先算出数组 $nums$ 的元素总和，记为 $s$。

如果 $target \gt s$，那么我们可以将 $target$ 减去 $\lfloor \frac{target}{s} \rfloor \times s$，这样就可以将 $target$ 减小到 $[0, s)$ 的范围内。那么此时子数组的长度为 $a = \lfloor \frac{target}{s} \rfloor \times n$，其中 $n$ 是数组 $nums$ 的长度。

接下来，我们只需要在数组 $nums$ 中，找出长度最短的且元素和等于 $target$ 的子数组，或者长度最短的且前缀和加上后缀和等于 $target$，即子数组元素和等于 $s - target$ 的子数组，记长度为 $b$。我们可以通过前缀和加哈希表的方法，找出这样的子数组。

如果找到了这样的子数组，那么最终的答案就是 $a + b$。否则，答案就是 $-1$。

时间复杂度 $O(n)$，空间复杂度 $O(n)$。其中 $n$ 是数组 $nums$ 的长度。

class Solution:
  def minSizeSubarray(self, nums: List[int], target: int) -> int:
    s = sum(nums)
    n = len(nums)
    a = 0
    if target > s:
      a = n * (target // s)
      target -= target // s * s
    if target == s:
      return n
    pos = {0: -1}
    pre = 0
    b = inf
    for i, x in enumerate(nums):
      pre += x
      if (t := pre - target) in pos:
        b = min(b, i - pos[t])
      if (t := pre - (s - target)) in pos:
        b = min(b, n - (i - pos[t]))
      pos[pre] = i
    return -1 if b == inf else a + b

class Solution {
  public int minSizeSubarray(int[] nums, int target) {
    long s = Arrays.stream(nums).sum();
    int n = nums.length;
    int a = 0;
    if (target > s) {
      a = n * (target / (int) s);
      target -= target / s * s;
    }
    if (target == s) {
      return n;
    }
    Map<Long, Integer> pos = new HashMap<>();
    pos.put(0L, -1);
    long pre = 0;
    int b = 1 << 30;
    for (int i = 0; i < n; ++i) {
      pre += nums[i];
      if (pos.containsKey(pre - target)) {
        b = Math.min(b, i - pos.get(pre - target));
      }
      if (pos.containsKey(pre - (s - target))) {
        b = Math.min(b, n - (i - pos.get(pre - (s - target))));
      }
      pos.put(pre, i);
    }
    return b == 1 << 30 ? -1 : a + b;
  }
}

class Solution {
public:
  int minSizeSubarray(vector<int>& nums, int target) {
    long long s = accumulate(nums.begin(), nums.end(), 0LL);
    int n = nums.size();
    int a = 0;
    if (target > s) {
      a = n * (target / s);
      target -= target / s * s;
    }
    if (target == s) {
      return n;
    }
    unordered_map<int, int> pos{{0, -1}};
    long long pre = 0;
    int b = 1 << 30;
    for (int i = 0; i < n; ++i) {
      pre += nums[i];
      if (pos.count(pre - target)) {
        b = min(b, i - pos[pre - target]);
      }
      if (pos.count(pre - (s - target))) {
        b = min(b, n - (i - pos[pre - (s - target)]));
      }
      pos[pre] = i;
    }
    return b == 1 << 30 ? -1 : a + b;
  }
};

func minSizeSubarray(nums []int, target int) int {
  s := 0
  for _, x := range nums {
    s += x
  }
  n := len(nums)
  a := 0
  if target > s {
    a = n * (target / s)
    target -= target / s * s
  }
  if target == s {
    return n
  }
  pos := map[int]int{0: -1}
  pre := 0
  b := 1 << 30
  for i, x := range nums {
    pre += x
    if j, ok := pos[pre-target]; ok {
      b = min(b, i-j)
    }
    if j, ok := pos[pre-(s-target)]; ok {
      b = min(b, n-(i-j))
    }
    pos[pre] = i
  }
  if b == 1<<30 {
    return -1
  }
  return a + b
}

function minSizeSubarray(nums: number[], target: number): number {
  const s = nums.reduce((a, b) => a + b);
  const n = nums.length;
  let a = 0;
  if (target > s) {
    a = n * ((target / s) | 0);
    target -= ((target / s) | 0) * s;
  }
  if (target === s) {
    return n;
  }
  const pos: Map<number, number> = new Map();
  let pre = 0;
  pos.set(0, -1);
  let b = Infinity;
  for (let i = 0; i < n; ++i) {
    pre += nums[i];
    if (pos.has(pre - target)) {
      b = Math.min(b, i - pos.get(pre - target)!);
    }
    if (pos.has(pre - (s - target))) {
      b = Math.min(b, n - (i - pos.get(pre - (s - target))!));
    }
    pos.set(pre, i);
  }
  return b === Infinity ? -1 : a + b;
}

方法二

class Solution {
  public int shortestSubarray(int[] nums, int k) {
    int n = nums.length;

    int minLength = n * 2 + 1;
    int l = 0;
    int sum = 0;

    for (int r = 0; r < n * 2; r++) {
      int start = l % n;
      int end = r % n;
      sum += nums[end];

      while (sum > k && l <= r) {
        start = l % n;
        sum -= nums[start];
        l++;
      }

      if (sum == k) {
        minLength = Math.min(minLength, r - l + 1);
        start = l % n;
        sum -= nums[start];
        l++;
      }
    }

    return minLength == n * 2 + 1 ? -1 : minLength;
  }
  public int minSizeSubarray(int[] nums, int target) {
    int n = nums.length;
    int sum = 0;

    for (int num : nums) {
      sum += num;
    }
    int k = target % sum;
    int ans = target / sum * n;
    if (k == 0) {
      return ans;
    }
    int res = shortestSubarray(nums, k);
    return res == -1 ? -1 : ans + res;
  }
}