算法训练+题解

苏瑾儿

1年前更新

831

文章目录[隐藏]

分割线－下方题解可以自己思考思考再看答案
分割线尾部－下方题解
方法一：前缀和
答案：
- Python↓
- JAVA↓
- C#↓
- C++↓
- C语言↓
- JavaScript↓
- Go语言↓

题目

给你一个长度为 n 的数组 nums ，该数组由从 1 到 n 的不同整数组成。另给你一个正整数 k 。

统计并返回 nums 中的 中位数 等于 k 的非空子数组的数目。

注意：

数组的中位数是按递增顺序排列后位于中间的那个元素，如果数组长度为偶数，则中位数是位于中间靠左的那个元素。
- 例如，[2,3,1,4] 的中位数是 2 ，[8,4,3,5,1] 的中位数是 4 。
子数组是数组中的一个连续部分。

示例

示例 1：

输入：nums = [3,2,1,4,5], k = 4
输出：3
解释：中位数等于 4 的子数组有：[4]、[4,5] 和 [1,4,5] 。

示例 2：

输入：nums = [2,3,1], k = 3
输出：1
解释：[3] 是唯一一个中位数等于 3 的子数组。

提示：

n == nums.length
1 <= n <= 10⁵
1 <= nums[i], k <= n
nums 中的整数互不相同

分割线－下方题解可以自己思考思考再看答案

分割线尾部－下方题解

方法一：前缀和

由于数组 nums 的长度是 n ，数组由从 1 到 n 的不同整数组成，因此数组中的元素各不相同，满足 1 小于等于 K 小于等于 n 的正整数 K 的数组中恰好出现一次。

用 kIndex 表示正整数 K 在数组 nums 中下标。根据中位数的定义，中位数等于 K 的非空子数组应满足以下条件：

子数组的开始下标小于等于 kIndex 且结束下标大于等于 kIndex ；
子数组中的大于 K 的元素个数与小于 K 的元素个数之差为 0 或 1.

为了计算每个子数组中的大于 K 的元素个数与小于 K 的元素个数之差，需要将原始数组做转换，将大于 K 的元素转换成 1 ，小于 K 的元素转换成 -1 ，等于 K 的元素转换成 0 ，转换后的数组中，每个子数组的元素和为对应的原始子数组中的大于 K 的元素个数与小于 K 的元素个数之差。

为了在转换后的数组中寻找符号要求的子数组，可以计算转换后的数组的前缀和。感觉前缀和寻找符号要求的子数组。规定空前缀的前缀和是 0 且对应下标 -1 。

如果存在下标 left 和 right 满足 -1 小于等于 left 小于等于 kIndex 小于等于 right 小于等于 n 且下标 right 处的前缀和与下标 left 处的前缀和之差为 0 或 1，则等价与下标范围 [left + 1,right] 包含下标 kIndex 且该下标范围的转换后的子数组的元素和为 0 或 1，对应该下标范围的原始子数组的中位数等于 K。

根据上述分析，可以从左到右遍历数组 nums ，遍历过程中计算转换后的数组的前缀和，并计算中位数等于 K 的非空子数组的数目。

使用哈希表记录转换后的数组的每个前缀和的出现次数。由于空前缀的前缀和是 0 ，因此首先将前缀和 0 与次数 1 存入哈希表。

用 sum 表示转换后的数组的前缀和，遍历过程中维护 sum 的值。对于 0 小于等于 i 小于等于 n ，当遍历到下标 i 时，更新 sum 的值，然后执行如下操作：

如果 i < kIndex ，则下标 i + 1 可以作为中位数等于 K 的非空子数组的开始下标，将 sum 在哈希表中的出现次数加 1 ；
如果 i 大于等于 kIndex ，则下标 i 可以作为中位数等于 K 的非空子数组的结束下标，从哈希表中获得前缀和 sum 的出现次数 prev0 与前缀和sum - 1 的出现次数 prev1 ，则以下标 i 作为结束下标且中位数等于 K 的非空子数组的数目是 prev0 + prev1 ，将答案增加 prev0 + prev1 。

遍历结束之后，即可得到中位数等于 K 的非空子数组的数目。

答案：

Python↓

class Solution:
    def sign(self, num: int) -> int:
        return (num > 0) - (num < 0)

    def countSubarrays(self, nums: List[int], k: int) -> int:
        kIndex = nums.index(k)
        ans = 0
        counts = Counter()
        counts[0] = 1
        sum = 0
        for i, num in enumerate(nums):
            sum += self.sign(num - k)
            if i < kIndex:
                counts[sum] += 1
            else:
                prev0 = counts[sum]
                prev1 = counts[sum - 1]
                ans += prev0 + prev1
        return ans

JAVA↓

class Solution {
    public int countSubarrays(int[] nums, int k) {
        int n = nums.length;
        int kIndex = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == k) {
                kIndex = i;
                break;
            }
        }
        int ans = 0;
        Map<Integer, Integer> counts = new HashMap<Integer, Integer>();
        counts.put(0, 1);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += sign(nums[i] - k);
            if (i < kIndex) {
                counts.put(sum, counts.getOrDefault(sum, 0) + 1);
            } else {
                int prev0 = counts.getOrDefault(sum, 0);
                int prev1 = counts.getOrDefault(sum - 1, 0);
                ans += prev0 + prev1;
            }
        }
        return ans;
    }

    public int sign(int num) {
        if (num == 0) {
            return 0;
        }
        return num > 0 ? 1 : -1;
    }
}

C#↓

public class Solution {
    public int CountSubarrays(int[] nums, int k) {
        int n = nums.Length;
        int kIndex = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == k) {
                kIndex = i;
                break;
            }
        }
        int ans = 0;
        IDictionary<int, int> counts = new Dictionary<int, int>();
        counts.Add(0, 1);
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += sign(nums[i] - k);
            if (i < kIndex) {
                if (!counts.ContainsKey(sum)) {
                    counts.Add(sum, 1);
                } else {
                    counts[sum]++;
                }
            } else {
                int prev0 = counts.ContainsKey(sum) ? counts[sum] : 0;
                int prev1 = counts.ContainsKey(sum - 1) ? counts[sum - 1] : 0;
                ans += prev0 + prev1;
            }
        }
        return ans;
    }

    public int sign(int num) {
        if (num == 0) {
            return 0;
        }
        return num > 0 ? 1 : -1;
    }
}

C++↓

class Solution {
public:
    inline int sign(int num) {
        if (num == 0) {
            return 0;
        }
        return num > 0 ? 1 : -1;
    }

    int countSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        int kIndex = -1;
        for (int i = 0; i < n; i++) {
            if (nums[i] == k) {
                kIndex = i;
                break;
            }
        }
        int ans = 0;
        unordered_map<int, int> counts;
        counts[0] = 1;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += sign(nums[i] - k);
            if (i < kIndex) {
                counts[sum]++;
            } else {
                int prev0 = counts[sum];
                int prev1 = counts[sum - 1];
                ans += prev0 + prev1;
            }
        }
        return ans;
    }
};

C语言↓

typedef struct {
    int key;
    int val;
    UT_hash_handle hh;
} HashItem; 

HashItem *hashFindItem(HashItem **obj, int key) {
    HashItem *pEntry = NULL;
    HASH_FIND_INT(*obj, &key, pEntry);
    return pEntry;
}

bool hashAddItem(HashItem **obj, int key, int val) {
    if (hashFindItem(obj, key)) {
        return false;
    }
    HashItem *pEntry = (HashItem *)malloc(sizeof(HashItem));
    pEntry->key = key;
    pEntry->val = val;
    HASH_ADD_INT(*obj, key, pEntry);
    return true;
}

bool hashSetItem(HashItem **obj, int key, int val) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        hashAddItem(obj, key, val);
    } else {
        pEntry->val = val;
    }
    return true;
}

int hashGetItem(HashItem **obj, int key, int defaultVal) {
    HashItem *pEntry = hashFindItem(obj, key);
    if (!pEntry) {
        return defaultVal;
    }
    return pEntry->val;
}

void hashFree(HashItem **obj) {
    HashItem *curr = NULL, *tmp = NULL;
    HASH_ITER(hh, *obj, curr, tmp) {
        HASH_DEL(*obj, curr);  
        free(curr);             
    }
}

static inline int sign(int num) {
    if (num == 0) {
        return 0;
    }
    return num > 0 ? 1 : -1;
}

int countSubarrays(int* nums, int numsSize, int k) {
    int kIndex = -1;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == k) {
            kIndex = i;
            break;
        }
    }
    int ans = 0;
    HashItem *counts = NULL;
    hashAddItem(&counts, 0, 1);
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += sign(nums[i] - k);
        if (i < kIndex) {
            hashSetItem(&counts, sum, hashGetItem(&counts, sum, 0) + 1);
        } else {
            int prev0 = hashGetItem(&counts, sum, 0);
            int prev1 = hashGetItem(&counts, sum - 1, 0);
            ans += prev0 + prev1;
        }
    }
    hashFree(&counts);
    return ans;
}

JavaScript↓

var countSubarrays = function(nums, k) {
    const n = nums.length;
    let kIndex = -1;
    for (let i = 0; i < n; i++) {
        if (nums[i] === k) {
            kIndex = i;
            break;
        }
    }
    let ans = 0;
    const counts = new Map();
    counts.set(0, 1);
    let sum = 0;
    for (let i = 0; i < n; i++) {
        sum += sign(nums[i] - k);
        if (i < kIndex) {
            counts.set(sum, (counts.get(sum) || 0) + 1);
        } else {
            const prev0 = (counts.get(sum) || 0);
            const prev1 = (counts.get(sum - 1) || 0);
            ans += prev0 + prev1;
        }
    }
    return ans;
}

const sign = (num) => {
    if (num === 0) {
        return 0;
    }
    return num > 0 ? 1 : -1;
};

Go语言↓

func countSubarrays(nums []int, k int) int {
    kIndex := -1
    for i, num := range nums {
        if num == k {
            kIndex = i
            break
        }
    }
    ans := 0
    counts := map[int]int{}
    counts[0] = 1
    sum := 0
    for i, num := range nums {
        sum += sign(num - k)
        if i < kIndex {
            counts[sum]++
        } else {
            prev0 := counts[sum]
            prev1 := counts[sum-1]
            ans += prev0 + prev1
        }
    }
    return ans
}

func sign(num int) int {
    if num == 0 {
        return 0
    }
    if num > 0 {
        return 1
    }
    return -1
}

不要问为什么只有这几种答案，问就是作者目前只掌握这几个哦~ (嘻~

哈希表不懂的小伙伴可以去网上搜搜了解一下，或者下方评论一下我再出一个帖子发哈希表的- ̗̀(๑ᵔ⌔ᵔ๑)( •͈ᴗ⁃͈)ᓂ- - -♡

1人已评分