Java缺失區(qū)間的查找方法

更新時間：2025年02月11日 08:27:05 作者：東百牧碼人

在 Java 的算法世界里,有許多有趣又具有挑戰(zhàn)性的問題等待我們去探索,今天,跟著小編一起來深入研究缺失區(qū)間的查找秘籍,文中有詳細的代碼示例供大家參考,需要的朋友可以參考下

問題描述

問題編號為 163，題目要求我們在給定的閉區(qū)間 [lower, upper] 內，找出那些在整數數組 nums 中缺失的數字區(qū)間。這就好比我們有一個完整的數字區(qū)間，但其中部分數字被拿走了，我們需要找出那些空缺的部分。

解題思路與過程剖析

方法簽名

public List<List<Integer>> findMissingRanges(int[] nums, int lower, int upper)

這個方法接收三個參數：一個整數數組 nums，以及兩個整數 lower 和 upper，它的任務是返回一個包含所有缺失區(qū)間的列表。每個缺失區(qū)間都由一個包含兩個整數的列表表示，分別是區(qū)間的起始和結束值。

初始化操作

List<List<Integer>> res = new ArrayList<>();
long pre = (long) lower - 1;

這里，我們創(chuàng)建了一個 res 列表，用于存儲最終的結果。而 pre 變量被初始化為 lower - 1，它的作用是記錄前一個檢查過的數字，方便我們后續(xù)判斷是否存在缺失區(qū)間。使用 long 類型是為了避免可能出現(xiàn)的整數溢出問題。

數組遍歷

for (int i = 0; i <= nums.length; i++) {
    long cur = i == nums.length ? (long) upper + 1 : nums[i];

我們通過一個 for 循環(huán)來遍歷數組 nums。需要注意的是，循環(huán)條件是 i <= nums.length，這意味著我們會多進行一次迭代。在最后一次迭代時，cur 會被設為 upper + 1，這樣做是為了確保我們能檢查到區(qū)間 [lower, upper] 的最后一個數字。

檢查缺失區(qū)間

if (cur - pre > 1) {
    List<Integer> list = new ArrayList<>();
    list.add((int) pre + 1);
    list.add((int) cur - 1);
    res.add(list);
}

在每次迭代中，我們會比較 cur 和 pre 的差值。如果差值大于 1，說明在 pre 和 cur 之間存在缺失的數字，我們就創(chuàng)建一個新的區(qū)間，起始值為 pre + 1，結束值為 cur - 1，并將這個區(qū)間添加到結果列表 res 中。

更新 pre

pre = cur;

為了確保下一次檢查的準確性，我們將 pre 更新為當前的 cur，這樣在下次迭代時，我們就能基于新的 pre 值繼續(xù)判斷是否存在缺失區(qū)間。

返回結果

return res;

最后，我們返回包含所有缺失區(qū)間的列表 res，這就是我們整個算法的最終輸出。

完整代碼

class Solution{
    publicList<List<Integer>>findMissingRanges(int[] nums,int lower,int upper){
        List<List<Integer>> res =newArrayList<>();
        long pre =(long) lower -1;
        for(int i =0; i <= nums.length; i++){
            long cur = i == nums.length ?(long) upper +1: nums[i];
            if(cur - pre >1){
                List<Integer> list =newArrayList<>();
                list.add((int) pre +1);
                list.add((int) cur -1);
                res.add(list);
            }
            pre = cur;
        }
        return res;
    }
}