LeetCode 5. Longest Palindromic Substring

问题描述



给定一个整数数组 nums 和一个整数 k。当子数组中有 k 个奇数时，称之为 nice。



要求返回 nice 子数组的个数。



栗 1：



输入: nums = [1,1,2,1,1], k = 3
输出: 2

解释：
包含 3 个奇数的子数组有：[1,1,2,1]，[1,2,1,1]



栗 2：

输入：nums = [2,4,6], k = 1
输出：0

解释：
无奇数。



栗 3：

输入: nums = [2,2,2,1,2,2,1,2,2,2], k = 2
输出: 16



注意：

• 1 <= nums.length <= 50000

• 1 <= nums[i] <= 10^5

• 1 <= k <= nums.length



想看英文原文的戳这里。



解题思路



题目要求子数组中只需包含 k 个奇数，因此其可以与任意个数的偶数进行组合。



同时 k 个奇数不一定是连续的，有可能掺杂着偶数。由于子数组的连续性， k 个奇数之间的偶数是必须包含的。当我们找到 k 个奇数时，需要考虑其与前后偶数的组合性。



举个栗子，比如 nums = [2, 2, 1, 2, 3, 4, 6, 8], k = 2。



子数组中需包含 2 个奇数，该数组中奇数为 1、3。显然， [1, 2, 3] 是子数组中必须要包含的元素。而左边的偶数 [2, 2] 和右边的偶数 [4, 6, 8] 则是可选的。它们的组合情况如下：



• 左边有 [], [2], [2, 2] 三种组合。

• 右边有 [], [4], [6], [4, 6, 8] 四种组合。



因此，左右两两组合总数为 3 * 4 = 12 。



稍微观察一下，我们可以发现：当有 n 个偶数时，组合数为 n + 1。因此，转换下思路，只需要求出左右两边偶数的个数即可。



而如何求得偶数个数呢？也比较简单，通过记录两个相邻奇数的下标，相减即可。但有种边界情况需要考虑：第一个出现的奇数，它前面没有奇数；最后一个出现的奇数，它后面有没奇数。



还是拿上面的栗子说明。



• 第一个奇数 1 的下标是 2，可默认前一个奇数下标为 0，那么偶数个数为 2 - 0 = 2。

• 最后一个奇数 3 的下标是 4，可默认最后一个奇数下标为 数组长度 - 1，那么偶数个数为 7 - 4 = 3。



当然，k 个奇数的组合方式可能不止一种，那么就需要遍历每 k 个奇数，求出它与偶数的组合数，最终得到总的组合数。



比如 nums = [2, 2, 1, 2, 3, 4, 5, 6], k = 2，奇数为 1、3、5。那么 k 个奇数的可能取值为 1、3、3、5，这里需要分别计算出它们与偶数的组合数。



注意：当取 1、3 时，由于它后面还有一个奇数 5，因此计算右边偶数个数时，只需计算到 5 的位置。



总体思路如下：



• 首先取出 k 个奇数，假设其起始下标为 [m, n]。

• 将 m 与左边相邻的奇数下标做计算，求出左边组合数个数 left。

• 将 n 与右边相邻的奇数下标做计算，求出右边组合数个数 right。

• 左右两边组合数相乘，即为这个 k 个奇数的组合数： left * right。

• 向后遍历，继续取出 k 个奇数，重复以上步骤。即始终保持 k 个奇数的窗口，不断向后移动。



解法 1



这种解法比较容易理解，就是上面阐述的思路。



• 遍历数组，记录所有奇数的下标。

• 遍历下标列表，分别求出 k 个奇数左右两边的组合数，然后相乘。

• 注意考虑第一个奇数和最后一个奇数的情况。



代码如下：



var numberOfSubarrays = function (nums, k) {
  if (!nums) {
    return 0;
  }
  let sum = 0;
  // 奇数的 index 列表
  let oddList = [];
  nums.forEach((element, index) => {
    if (element % 2 === 1) {
      oddList.push(index);
    }
  });
  let i = 0;
  while (i <= oddList.length - k) {
    let left = 0;
    let right = 0;
    // 计算左边的组合数，从原数组第一个数开始
    if (i === 0) {
      left = oddList[i] + 1;
    } else {
      // 计算相邻的个数
      left = oddList[i] - oddList[i - 1];
    }
    // 覆盖 k 个奇数
    // 计算右边的组合数
    const endIndex = i + k - 1;
    // 最后一个，组合个数可一直到原数组末尾
    if (endIndex == oddList.length - 1) {
      right = nums.length - oddList[endIndex];
    } else {
      // 计算相邻的个数
      right = oddList[endIndex + 1] - oddList[endIndex];
    }
    sum += left * right;
    i += 1;
  }
  return sum;
};



解法 2



思路上大同小异，只不过不需要事先计算出奇数下标列表，而是在遍历过程中判断是否达到了 k 个奇数的条件。如果满足条件，则计算组合数；如果超过了 k 个奇数，则需更新 k 个奇数列表，再进行计算。



以下代码是采用记录开始窗口的下标，然后不断滑动窗口更新下标的方式。也可以采用操作窗口数组的方式，当元素个数大于 k 时，删除第一个元素，让其始终保持 k 个数。



js 代码如下：



var numberOfSubarrays = function (nums, k) {
  if (!nums) {
    return 0;
  }
  let sum = 0;
  // 记录上一次 k 个奇数数的第一个数下标
  let oddIndex = 0
  // 奇数的 index 列表，默认填入 -1
  let oddList = [-1];
  nums.forEach((element, index) => {
    if (element % 2 === 1) {
      oddList.push(index)
      // 当已经有 k 个奇数，更新记录下标
      if (oddList.length - oddIndex - 1 > k) {
        oddIndex += 1
      }
    }
	// 满足 k 个奇数
    if (oddList.length - oddIndex - 1 === k) {
      sum += oddList[oddIndex + 1] - oddList[oddIndex]
    }
  });
  return sum
};