跳转至

3452. 好数字之和

题目描述

给定一个整数数组 nums 和一个整数 k，如果元素 nums[i] 严格 大于下标 i - k 和 i + k 处的元素（如果这些元素存在），则该元素 nums[i] 被认为是 好 的。如果这两个下标至少一个不存在，那么 nums[i] 仍然被认为是 好 的。

返回数组中所有 好 元素的 和。

 

示例 1：

输入： nums = [1,3,2,1,5,4], k = 2

输出： 12

解释：

好的数字包括 nums[1] = 3，nums[4] = 5 和 nums[5] = 4，因为它们严格大于下标 i - k 和 i + k 处的数字。

示例 2：

输入： nums = [2,1], k = 1

输出： 2

解释：

唯一的好数字是 nums[0] = 2，因为它严格大于 nums[1]。

 

提示：

  • 2 <= nums.length <= 100
  • 1 <= nums[i] <= 1000
  • 1 <= k <= floor(nums.length / 2)

解法

方法一：遍历

我们可以遍历数组 \(\textit{nums}\)，对于每个元素 \(\textit{nums}[i]\)，检查是否满足条件：

  • 如果 \(i \ge k\) 且 \(\textit{nums}[i] \le \textit{nums}[i - k]\)，则 \(\textit{nums}[i]\) 不是好数字；
  • 如果 \(i + k < \textit{len}(\textit{nums})\) 且 \(\textit{nums}[i] \le \textit{nums}[i + k]\)，则 \(\textit{nums}[i]\) 不是好数字。
  • 否则，\(\textit{nums}[i]\) 是好数字，我们将其累加到答案中。

遍历结束后，返回答案即可。

时间复杂度 \(O(n)\)，其中 \(n\) 是数组 \(\textit{nums}\) 的长度。空间复杂度 \(O(1)\)。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
class Solution:
    def sumOfGoodNumbers(self, nums: List[int], k: int) -> int:
        ans = 0
        for i, x in enumerate(nums):
            if i >= k and x <= nums[i - k]:
                continue
            if i + k < len(nums) and x <= nums[i + k]:
                continue
            ans += x
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution {
    public int sumOfGoodNumbers(int[] nums, int k) {
        int ans = 0;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            if (i >= k && nums[i] <= nums[i - k]) {
                continue;
            }
            if (i + k < n && nums[i] <= nums[i + k]) {
                continue;
            }
            ans += nums[i];
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int sumOfGoodNumbers(vector<int>& nums, int k) {
        int ans = 0;
        int n = nums.size();
        for (int i = 0; i < n; ++i) {
            if (i >= k && nums[i] <= nums[i - k]) {
                continue;
            }
            if (i + k < n && nums[i] <= nums[i + k]) {
                continue;
            }
            ans += nums[i];
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
func sumOfGoodNumbers(nums []int, k int) (ans int) {
    for i, x := range nums {
        if i >= k && x <= nums[i-k] {
            continue
        }
        if i+k < len(nums) && x <= nums[i+k] {
            continue
        }
        ans += x
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
function sumOfGoodNumbers(nums: number[], k: number): number {
    const n = nums.length;
    let ans = 0;
    for (let i = 0; i < n; ++i) {
        if (i >= k && nums[i] <= nums[i - k]) {
            continue;
        }
        if (i + k < n && nums[i] <= nums[i + k]) {
            continue;
        }
        ans += nums[i];
    }
    return ans;
}

评论