如何修改初始算法找到包含指定数值范围的最短数组子序列？

问题描述 #

需要找到整数数组中包含[a,...,b]所有整数的最短子序列。初始思路是将数组元素加入集合，直到集合包含整个范围的元素，但仅能找到第一个满足条件的子数组，无法获取更短的序列。

初始代码如下：

int shortestFragmentSize(std::vector<int> &values, int a, int b) {
    std::unordered_set<int> range;
    const int range_size = (b - a) + 1;
    size_t lidx = 0;
    size_t ridx = 0;
    for(size_t i = 0; i < values.size(); ++i) {
        if( range.size() == range_size ) {
            break;
        }
        const int val = values.at(i);
        if ( val >= a && val <= b ) {
            if( range.find(val) == range.end() ) {
                range.insert(val);
            }
        }
        ridx += 1;
    }
    if( range.size() != range_size )
        return -1;
    return (ridx - lidx);
}

在示例数组[2, 1, 4, 3, 2, 1, 1, 4]、a=2、b=4的情况下，初始算法会选择前4个元素，但实际最短子序列是[4,3,2]，长度应为3。

改进思路 #

初始代码的问题在于仅找到第一个满足条件的窗口后就停止遍历，没有尝试缩小窗口范围，也没有检查后续可能存在的更短有效窗口。可以基于**滑动窗口（双指针）**思路修改：

• 用哈希表记录窗口内目标元素的出现次数（而非仅判断存在性）
• 右指针扩展窗口，直到包含所有目标元素
• 左指针尝试缩小窗口，同时维护窗口内的元素计数，直到窗口不再满足条件
• 过程中持续记录最小的有效窗口长度

修改后的代码 #

#include <vector>
#include <unordered_map>
#include <climits>
#include <algorithm>

int shortestFragmentSize(std::vector<int> &values, int a, int b) {
    const int range_size = b - a + 1;
    std::unordered_map<int, int> elem_count;
    int left = 0;
    int min_len = INT_MAX;
    int covered = 0;

    for (int right = 0; right < values.size(); ++right) {
        int curr_val = values[right];
        // 跳过不在目标范围内的元素
        if (curr_val < a || curr_val > b) {
            continue;
        }

        // 更新当前元素的计数，若首次加入则增加覆盖数
        if (elem_count[curr_val] == 0) {
            covered++;
        }
        elem_count[curr_val]++;

        // 当窗口覆盖所有目标元素时，尝试缩小左边界
        while (covered == range_size) {
            // 更新最小窗口长度
            min_len = std::min(min_len, right - left + 1);

            int left_val = values[left];
            if (left_val >= a && left_val <= b) {
                elem_count[left_val]--;
                // 若该元素计数归零，说明窗口不再覆盖所有目标
                if (elem_count[left_val] == 0) {
                    covered--;
                }
            }
            left++;
        }
    }

    // 若未找到有效窗口返回-1，否则返回最小长度
    return min_len == INT_MAX ? -1 : min_len;
}

代码说明 #

1. 计数与覆盖数：elem_count记录窗口内每个目标元素的出现次数，covered记录已覆盖的不同目标元素数量，当covered等于range_size时，窗口有效。
2. 右指针扩展：遍历数组，将目标元素加入窗口并更新计数和覆盖数。
3. 左指针收缩：窗口有效时，尝试移动左指针缩小窗口，同时更新计数，若某元素计数归零则减少覆盖数，直到窗口无效。
4. 最小长度记录：每次有效窗口收缩时，更新最小窗口长度。

示例验证 #

对于数组[2, 1, 4, 3, 2, 1, 1, 4]、a=2、b=4：

• 右指针遍历到索引4（元素2）时，窗口[0,4]有效，此时开始收缩左指针
• 左指针移动到索引2（元素4）时，窗口[2,4]包含4、3、2，覆盖所有目标元素，长度为3，是当前最小长度
• 后续遍历不会找到更短的有效窗口，最终返回3

内容的提问来源于stack exchange，提问作者binaryBigInt