返回介绍

solution / 3000-3099 / 3034.Number of Subarrays That Match a Pattern I / README_EN

发布于 2024-06-17 01:02:57 字数 6162 浏览 0 评论 0 收藏 0

3034. Number of Subarrays That Match a Pattern I

中文文档

Description

You are given a 0-indexed integer array nums of size n, and a 0-indexed integer array pattern of size m consisting of integers -1, 0, and 1.

A subarray nums[i..j] of size m + 1 is said to match the pattern if the following conditions hold for each element pattern[k]:

  • nums[i + k + 1] > nums[i + k] if pattern[k] == 1.
  • nums[i + k + 1] == nums[i + k] if pattern[k] == 0.
  • nums[i + k + 1] < nums[i + k] if pattern[k] == -1.

Return _the count of subarrays in_ nums _that match the_ pattern.

 

Example 1:

Input: nums = [1,2,3,4,5,6], pattern = [1,1]
Output: 4
Explanation: The pattern [1,1] indicates that we are looking for strictly increasing subarrays of size 3. In the array nums, the subarrays [1,2,3], [2,3,4], [3,4,5], and [4,5,6] match this pattern.
Hence, there are 4 subarrays in nums that match the pattern.

Example 2:

Input: nums = [1,4,4,1,3,5,5,3], pattern = [1,0,-1]
Output: 2
Explanation: Here, the pattern [1,0,-1] indicates that we are looking for a sequence where the first number is smaller than the second, the second is equal to the third, and the third is greater than the fourth. In the array nums, the subarrays [1,4,4,1], and [3,5,5,3] match this pattern.
Hence, there are 2 subarrays in nums that match the pattern.

 

Constraints:

  • 2 <= n == nums.length <= 100
  • 1 <= nums[i] <= 109
  • 1 <= m == pattern.length < n
  • -1 <= pattern[i] <= 1

Solutions

Solution 1: Enumeration

We can enumerate all subarrays of array nums with a length of $m + 1$, and then check whether they match the pattern array pattern. If they do, we increment the answer by one.

The time complexity is $O(n \times m)$, where $n$ and $m$ are the lengths of the arrays nums and pattern respectively. The space complexity is $O(1)$.

class Solution:
  def countMatchingSubarrays(self, nums: List[int], pattern: List[int]) -> int:
    def f(a: int, b: int) -> int:
      return 0 if a == b else (1 if a < b else -1)

    ans = 0
    for i in range(len(nums) - len(pattern)):
      ans += all(
        f(nums[i + k], nums[i + k + 1]) == p for k, p in enumerate(pattern)
      )
    return ans
class Solution {
  public int countMatchingSubarrays(int[] nums, int[] pattern) {
    int n = nums.length, m = pattern.length;
    int ans = 0;
    for (int i = 0; i < n - m; ++i) {
      int ok = 1;
      for (int k = 0; k < m && ok == 1; ++k) {
        if (f(nums[i + k], nums[i + k + 1]) != pattern[k]) {
          ok = 0;
        }
      }
      ans += ok;
    }
    return ans;
  }

  private int f(int a, int b) {
    return a == b ? 0 : (a < b ? 1 : -1);
  }
}
class Solution {
public:
  int countMatchingSubarrays(vector<int>& nums, vector<int>& pattern) {
    int n = nums.size(), m = pattern.size();
    int ans = 0;
    auto f = [](int a, int b) {
      return a == b ? 0 : (a < b ? 1 : -1);
    };
    for (int i = 0; i < n - m; ++i) {
      int ok = 1;
      for (int k = 0; k < m && ok == 1; ++k) {
        if (f(nums[i + k], nums[i + k + 1]) != pattern[k]) {
          ok = 0;
        }
      }
      ans += ok;
    }
    return ans;
  }
};
func countMatchingSubarrays(nums []int, pattern []int) (ans int) {
  f := func(a, b int) int {
    if a == b {
      return 0
    }
    if a < b {
      return 1
    }
    return -1
  }
  n, m := len(nums), len(pattern)
  for i := 0; i < n-m; i++ {
    ok := 1
    for k := 0; k < m && ok == 1; k++ {
      if f(nums[i+k], nums[i+k+1]) != pattern[k] {
        ok = 0
      }
    }
    ans += ok
  }
  return
}
function countMatchingSubarrays(nums: number[], pattern: number[]): number {
  const f = (a: number, b: number) => (a === b ? 0 : a < b ? 1 : -1);
  const n = nums.length;
  const m = pattern.length;
  let ans = 0;
  for (let i = 0; i < n - m; ++i) {
    let ok = 1;
    for (let k = 0; k < m && ok; ++k) {
      if (f(nums[i + k], nums[i + k + 1]) !== pattern[k]) {
        ok = 0;
      }
    }
    ans += ok;
  }
  return ans;
}
public class Solution {
  public int CountMatchingSubarrays(int[] nums, int[] pattern) {
    int n = nums.Length, m = pattern.Length;
    int ans = 0;
    for (int i = 0; i < n - m; ++i) {
      int ok = 1;
      for (int k = 0; k < m && ok == 1; ++k) {
        if (f(nums[i + k], nums[i + k + 1]) != pattern[k]) {
          ok = 0;
        }
      }
      ans += ok;
    }
    return ans;
  }

  private int f(int a, int b) {
    return a == b ? 0 : (a < b ? 1 : -1);
  }
}

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
    原文