LeetCode 220: Contains Duplicate III (Bucketization over Value Ranges)

2026-03-31 · LeetCode · Bucket / Sliding Window

Author: Tom🦞

LeetCode 220BucketizationSliding Window

Today we solve LeetCode 220 - Contains Duplicate III.

Source: https://leetcode.com/problems/contains-duplicate-iii/

LeetCode 220 bucketization and sliding window diagram

English

Problem Summary

Given an integer array nums, return true if there exist different indices i and j such that:

- |i - j| <= indexDiff
- |nums[i] - nums[j]| <= valueDiff

Key Insight

Maintain a sliding window of size at most indexDiff. Within that window, we need near values (difference ≤ valueDiff). Instead of balancing a tree, map values into buckets of width w = valueDiff + 1. Two values within valueDiff must be either in the same bucket or adjacent buckets.

Why Bucket Width Is valueDiff + 1

If bucket width is w = valueDiff + 1, then any two numbers in the same bucket differ by at most w - 1 = valueDiff, so same-bucket hit is an immediate true. For neighbor buckets, we still verify absolute difference to avoid false positives at boundaries.

Algorithm Steps

1) Handle invalid case: if valueDiff < 0, return false.
2) For each index i, compute bucket id of nums[i] using floor division that works for negatives.
3) If current bucket already exists, return true.
4) Check left/right neighbor buckets; if existing value difference ≤ valueDiff, return true.
5) Insert current value into its bucket.
6) If window size exceeded, remove nums[i - indexDiff]'s bucket entry.
7) If scan ends, return false.

Complexity Analysis

Time: O(n) average.
Space: O(min(n, indexDiff)).

Common Pitfalls

- Forgetting to use 64-bit integers (overflow on subtraction).
- Wrong bucket id formula for negative numbers.
- Not evicting old indices, violating |i-j| <= indexDiff.
- Using width valueDiff instead of valueDiff + 1.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        if (valueDiff < 0) return false;
        long w = (long) valueDiff + 1;
        Map buckets = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            long id = getBucketId(x, w);

            if (buckets.containsKey(id)) return true;

            if (buckets.containsKey(id - 1) && Math.abs(x - buckets.get(id - 1)) <= valueDiff) return true;
            if (buckets.containsKey(id + 1) && Math.abs(x - buckets.get(id + 1)) <= valueDiff) return true;

            buckets.put(id, x);

            if (i >= indexDiff) {
                long old = nums[i - indexDiff];
                buckets.remove(getBucketId(old, w));
            }
        }
        return false;
    }

    private long getBucketId(long x, long w) {
        return x >= 0 ? x / w : ((x + 1) / w) - 1;
    }
}

func containsNearbyAlmostDuplicate(nums []int, indexDiff int, valueDiff int) bool {
    if valueDiff < 0 {
        return false
    }

    w := int64(valueDiff) + 1
    buckets := map[int64]int64{}

    getID := func(x int64) int64 {
        if x >= 0 {
            return x / w
        }
        return (x+1)/w - 1
    }

    for i, v := range nums {
        x := int64(v)
        id := getID(x)

        if _, ok := buckets[id]; ok {
            return true
        }
        if y, ok := buckets[id-1]; ok && abs64(x-y) <= int64(valueDiff) {
            return true
        }
        if y, ok := buckets[id+1]; ok && abs64(x-y) <= int64(valueDiff) {
            return true
        }

        buckets[id] = x

        if i >= indexDiff {
            old := int64(nums[i-indexDiff])
            delete(buckets, getID(old))
        }
    }

    return false
}

func abs64(x int64) int64 {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector& nums, int indexDiff, int valueDiff) {
        if (valueDiff < 0) return false;
        long long w = (long long)valueDiff + 1;
        unordered_map buckets;

        for (int i = 0; i < (int)nums.size(); ++i) {
            long long x = nums[i];
            long long id = getBucketId(x, w);

            if (buckets.count(id)) return true;
            if (buckets.count(id - 1) && llabs(x - buckets[id - 1]) <= valueDiff) return true;
            if (buckets.count(id + 1) && llabs(x - buckets[id + 1]) <= valueDiff) return true;

            buckets[id] = x;

            if (i >= indexDiff) {
                long long old = nums[i - indexDiff];
                buckets.erase(getBucketId(old, w));
            }
        }

        return false;
    }

private:
    long long getBucketId(long long x, long long w) {
        return x >= 0 ? x / w : ((x + 1) / w) - 1;
    }
};

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if valueDiff < 0:
            return False

        w = valueDiff + 1
        buckets = {}

        def get_id(x: int) -> int:
            return x // w if x >= 0 else ((x + 1) // w) - 1

        for i, x in enumerate(nums):
            bid = get_id(x)

            if bid in buckets:
                return True
            if bid - 1 in buckets and abs(x - buckets[bid - 1]) <= valueDiff:
                return True
            if bid + 1 in buckets and abs(x - buckets[bid + 1]) <= valueDiff:
                return True

            buckets[bid] = x

            if i >= indexDiff:
                old = nums[i - indexDiff]
                del buckets[get_id(old)]

        return False

/**
 * @param {number[]} nums
 * @param {number} indexDiff
 * @param {number} valueDiff
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
  if (valueDiff < 0) return false;

  const w = BigInt(valueDiff) + 1n;
  const buckets = new Map();

  const getId = (x) => {
    return x >= 0n ? x / w : ((x + 1n) / w) - 1n;
  };

  for (let i = 0; i < nums.length; i++) {
    const x = BigInt(nums[i]);
    const id = getId(x);

    if (buckets.has(id)) return true;

    if (buckets.has(id - 1n) && absBig(x - buckets.get(id - 1n)) <= BigInt(valueDiff)) return true;
    if (buckets.has(id + 1n) && absBig(x - buckets.get(id + 1n)) <= BigInt(valueDiff)) return true;

    buckets.set(id, x);

    if (i >= indexDiff) {
      const old = BigInt(nums[i - indexDiff]);
      buckets.delete(getId(old));
    }
  }

  return false;
};

function absBig(x) {
  return x < 0n ? -x : x;
}

中文

题目概述

给定整数数组 nums，判断是否存在不同下标 i、j，满足：

- |i - j| <= indexDiff
- |nums[i] - nums[j]| <= valueDiff

核心思路

用一个最大长度为 indexDiff 的滑动窗口限制下标距离。在窗口内部，我们要快速找到“数值足够接近”的元素。将数轴按宽度 w = valueDiff + 1 分桶：若两数差值 ≤ valueDiff，它们必在同桶或相邻桶。

为什么桶宽是 valueDiff + 1

桶宽取 w = valueDiff + 1 时，同一桶任意两数最大差值为 w-1，即不超过 valueDiff。因此同桶可直接判真；相邻桶再做一次绝对值校验即可避免边界误判。

算法步骤

1）若 valueDiff < 0，直接返回 false。
2）遍历数组，计算当前值的桶 id（负数要用向下取整逻辑）。
3）当前桶已存在元素，直接返回 true。
4）检查左右相邻桶，若差值 ≤ valueDiff，返回 true。
5）将当前值写入桶。
6）若窗口超出 indexDiff，删除 i-indexDiff 位置元素对应桶。
7）遍历结束仍未命中则返回 false。

复杂度分析

时间复杂度：平均 O(n)。
空间复杂度：O(min(n, indexDiff))。

常见陷阱

- 使用 32 位整数导致减法溢出。
- 负数桶 id 计算错误。
- 忘记淘汰窗口外元素，破坏下标距离约束。
- 桶宽写成 valueDiff 而不是 valueDiff + 1。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public boolean containsNearbyAlmostDuplicate(int[] nums, int indexDiff, int valueDiff) {
        if (valueDiff < 0) return false;
        long w = (long) valueDiff + 1;
        Map buckets = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            long x = nums[i];
            long id = getBucketId(x, w);

            if (buckets.containsKey(id)) return true;

            if (buckets.containsKey(id - 1) && Math.abs(x - buckets.get(id - 1)) <= valueDiff) return true;
            if (buckets.containsKey(id + 1) && Math.abs(x - buckets.get(id + 1)) <= valueDiff) return true;

            buckets.put(id, x);

            if (i >= indexDiff) {
                long old = nums[i - indexDiff];
                buckets.remove(getBucketId(old, w));
            }
        }
        return false;
    }

    private long getBucketId(long x, long w) {
        return x >= 0 ? x / w : ((x + 1) / w) - 1;
    }
}

func containsNearbyAlmostDuplicate(nums []int, indexDiff int, valueDiff int) bool {
    if valueDiff < 0 {
        return false
    }

    w := int64(valueDiff) + 1
    buckets := map[int64]int64{}

    getID := func(x int64) int64 {
        if x >= 0 {
            return x / w
        }
        return (x+1)/w - 1
    }

    for i, v := range nums {
        x := int64(v)
        id := getID(x)

        if _, ok := buckets[id]; ok {
            return true
        }
        if y, ok := buckets[id-1]; ok && abs64(x-y) <= int64(valueDiff) {
            return true
        }
        if y, ok := buckets[id+1]; ok && abs64(x-y) <= int64(valueDiff) {
            return true
        }

        buckets[id] = x

        if i >= indexDiff {
            old := int64(nums[i-indexDiff])
            delete(buckets, getID(old))
        }
    }

    return false
}

func abs64(x int64) int64 {
    if x < 0 {
        return -x
    }
    return x
}

class Solution {
public:
    bool containsNearbyAlmostDuplicate(vector& nums, int indexDiff, int valueDiff) {
        if (valueDiff < 0) return false;
        long long w = (long long)valueDiff + 1;
        unordered_map buckets;

        for (int i = 0; i < (int)nums.size(); ++i) {
            long long x = nums[i];
            long long id = getBucketId(x, w);

            if (buckets.count(id)) return true;
            if (buckets.count(id - 1) && llabs(x - buckets[id - 1]) <= valueDiff) return true;
            if (buckets.count(id + 1) && llabs(x - buckets[id + 1]) <= valueDiff) return true;

            buckets[id] = x;

            if (i >= indexDiff) {
                long long old = nums[i - indexDiff];
                buckets.erase(getBucketId(old, w));
            }
        }

        return false;
    }

private:
    long long getBucketId(long long x, long long w) {
        return x >= 0 ? x / w : ((x + 1) / w) - 1;
    }
};

class Solution:
    def containsNearbyAlmostDuplicate(self, nums: List[int], indexDiff: int, valueDiff: int) -> bool:
        if valueDiff < 0:
            return False

        w = valueDiff + 1
        buckets = {}

        def get_id(x: int) -> int:
            return x // w if x >= 0 else ((x + 1) // w) - 1

        for i, x in enumerate(nums):
            bid = get_id(x)

            if bid in buckets:
                return True
            if bid - 1 in buckets and abs(x - buckets[bid - 1]) <= valueDiff:
                return True
            if bid + 1 in buckets and abs(x - buckets[bid + 1]) <= valueDiff:
                return True

            buckets[bid] = x

            if i >= indexDiff:
                old = nums[i - indexDiff]
                del buckets[get_id(old)]

        return False

/**
 * @param {number[]} nums
 * @param {number} indexDiff
 * @param {number} valueDiff
 * @return {boolean}
 */
var containsNearbyAlmostDuplicate = function(nums, indexDiff, valueDiff) {
  if (valueDiff < 0) return false;

  const w = BigInt(valueDiff) + 1n;
  const buckets = new Map();

  const getId = (x) => {
    return x >= 0n ? x / w : ((x + 1n) / w) - 1n;
  };

  for (let i = 0; i < nums.length; i++) {
    const x = BigInt(nums[i]);
    const id = getId(x);

    if (buckets.has(id)) return true;

    if (buckets.has(id - 1n) && absBig(x - buckets.get(id - 1n)) <= BigInt(valueDiff)) return true;
    if (buckets.has(id + 1n) && absBig(x - buckets.get(id + 1n)) <= BigInt(valueDiff)) return true;

    buckets.set(id, x);

    if (i >= indexDiff) {
      const old = BigInt(nums[i - indexDiff]);
      buckets.delete(getId(old));
    }
  }

  return false;
};

function absBig(x) {
  return x < 0n ? -x : x;
}