1
#include <stdbool.h>
2
#include <limits.h>
3

4
/* 值 → 最近一次出现的下标。开放寻址 + 线性探测，同一个值只保留最新下标，
5
   所以整张表只写不删，不需要墓碑。 */
6
#define CAP (1u << 18)                       /* 2 的幂：& (CAP-1) 代替取模 */
7
#define EMPTY LLONG_MIN
8

9
static long long key2[CAP];
10
static int       pos2[CAP];
11

12
static unsigned long long hash2(long long x) {
13
    unsigned long long h = (unsigned long long)x;
14
    h ^= h >> 33; h *= 0xff51afd7ed558ccdULL;
15
    h ^= h >> 33; h *= 0xc4ceb9fe1a85ec53ULL;
16
    h ^= h >> 33;
17
    return h;
18
}
19

20
static void clear2(void) {
21
    for (unsigned i = 0; i < CAP; i++) key2[i] = EMPTY;
22
}
23

24
bool containsNearbyDuplicate(int *nums, int numsSize, int k) {
25
    clear2();
26

27
    for (int i = 0; i < numsSize; i++) {
28
        long long v = nums[i];
29
        unsigned long long h = hash2(v) & (CAP - 1);
30

31
        while (key2[h] != EMPTY && key2[h] != v)
32
            h = (h + 1) & (CAP - 1);         /* 线性探测找位置 */
33

34
        if (key2[h] == v) {
35
            if (i - pos2[h] <= k) return true;   /* 距离够近，命中 */
36
            pos2[h] = i;                          /* 否则更新成最新下标 */
37
        } else {
38
            key2[h] = v;
39
            pos2[h] = i;
40
        }
41
    }
42
    return false;
43
}

1
function containsNearbyDuplicate(nums, k) {
2
  const last = new Map();          // 值 → 最近一次出现的下标
3

4
  for (let i = 0; i < nums.length; i++) {
5
    const j = last.get(nums[i]);
6
    if (j !== undefined && i - j <= k) return true;
7
    last.set(nums[i], i);          // 同一个值只留最新下标，天然完成「出窗」
8
  }
9
  return false;
10
}

1
#include <stdbool.h>
2
#include <stdlib.h>
3

4
/* 桶号 → 桶里那个元素的值。桶宽 w = t+1，同一个桶里任意两数之差 ≤ t，
5
   所以每个桶最多只需要留一个元素（要是有两个，早就返回 true 了）。
6
   元素滑出窗口时要删掉它所在的桶，所以这里用墓碑标记删除。 */
7
#define CAP3 (1u << 18)                      /* 窗口里最多 k+1 个桶，2^18 留足余量 */
8
#define EMPTY3 (1LL << 62)
9
#define TOMB3  (1LL << 61)
10

11
static long long key3[CAP3];
12
static long long val3[CAP3];
13

14
static unsigned long long hash3(long long x) {
15
    unsigned long long h = (unsigned long long)x;
16
    h ^= h >> 33; h *= 0xff51afd7ed558ccdULL;
17
    h ^= h >> 33; h *= 0xc4ceb9fe1a85ec53ULL;
18
    h ^= h >> 33;
19
    return h;
20
}
21

22
static long long floorDiv(long long a, long long b) {   /* b > 0 时向下取整 */
23
    long long q = a / b;
24
    if (a % b != 0 && a < 0) q--;                      /* C 的除法向零取整，负数要修正 */
25
    return q;
26
}
27

28
static long long get3(long long key) {
29
    unsigned long long h = hash3(key) & (CAP3 - 1);
30
    while (key3[h] != EMPTY3) {                        /* 墓碑要继续往后找 */
31
        if (key3[h] == key) return val3[h];
32
        h = (h + 1) & (CAP3 - 1);
33
    }
34
    return EMPTY3;
35
}
36

37
static void put3(long long key, long long val) {
38
    unsigned long long h = hash3(key) & (CAP3 - 1);
39
    while (key3[h] != EMPTY3 && key3[h] != TOMB3 && key3[h] != key)
40
        h = (h + 1) & (CAP3 - 1);
41
    key3[h] = key;
42
    val3[h] = val;                                     /* 墓碑位置可以复用 */
43
}
44

45
static void del3(long long key) {
46
    unsigned long long h = hash3(key) & (CAP3 - 1);
47
    while (key3[h] != EMPTY3) {
48
        if (key3[h] == key) { key3[h] = TOMB3; return; }
49
        h = (h + 1) & (CAP3 - 1);
50
    }
51
}
52

53
static void clear3(void) {
54
    for (unsigned i = 0; i < CAP3; i++) key3[i] = EMPTY3;
55
}
56

57
bool containsNearbyAlmostDuplicate(int *nums, int numsSize, int k, int t) {
58
    if (t < 0 || k < 0) return false;
59

60
    long long w = (long long)t + 1;      /* t 最大 2^31-1，先转 long long 再加一 */
61
    clear3();
62

63
    for (int i = 0; i < numsSize; i++) {
64
        long long v = nums[i];
65
        long long id = floorDiv(v, w);
66

67
        if (get3(id) != EMPTY3) return true;            /* 同一个桶，必然差 ≤ t */
68

69
        long long a = get3(id - 1);                     /* 左邻桶 */
70
        if (a != EMPTY3 && llabs(v - a) <= t) return true;
71

72
        long long b = get3(id + 1);                     /* 右邻桶 */
73
        if (b != EMPTY3 && llabs(v - b) <= t) return true;
74

75
        put3(id, v);
76

77
        if (i - k >= 0)                                 /* 下标滑出窗口，删掉它的桶 */
78
            del3(floorDiv((long long)nums[i - k], w));
79
    }
80
    return false;
81
}

1
function containsNearbyAlmostDuplicate(nums, k, t) {
2
  const w = t + 1;                 // 桶宽：同桶内任意两数之差 ≤ t
3
  const bucket = new Map();        // 桶号 → 桶里的那个下标（下标滑出窗口时要删）
4
  const idOf = (v) => Math.floor(v / w);   // Math.floor 对负数也是向下取整
5

6
  for (let i = 0; i < nums.length; i++) {
7
    const id = idOf(nums[i]);
8

9
    if (bucket.has(id)) return true;                 // 同一个桶，必然差 ≤ t
10

11
    const lo = bucket.get(id - 1);                   // 左邻桶
12
    if (lo !== undefined && nums[i] - nums[lo] <= t) return true;
13

14
    const hi = bucket.get(id + 1);                   // 右邻桶
15
    if (hi !== undefined && nums[hi] - nums[i] <= t) return true;
16

17
    bucket.set(id, i);
18

19
    if (i - k >= 0) bucket.delete(idOf(nums[i - k]));   // 移出窗口
20
  }
21
  return false;
22
}

1
int minOperations(int *nums, int numsSize, int x) {
2
    long long total = 0;
3
    for (int i = 0; i < numsSize; i++) total += nums[i];
4
    if (total < x) return -1;
5

6
    /* 从两端删掉的元素之和 = x，等价于「中间留下的那一段，和 = total - x」；
7
       操作数最少 = 中间这一段最长。 */
8
    long long target = total - x;
9
    long long sum = 0;
10
    int left = 0, right = 0, best = -1;
11

12
    while (right < numsSize) {
13
        sum += nums[right];              /* ① 右边界入窗 */
14
        right++;
15

16
        while (sum > target) {           /* ③ 全是正数，超了就一定能靠收缩降下来 */
17
            sum -= nums[left];
18
            left++;
19
        }
20
        if (sum == target && right - left > best)
21
            best = right - left;         /* ④ 收缩后记录：这一段越长，操作数越少 */
22
    }
23
    return best < 0 ? -1 : numsSize - best;
24
}

1
function minOperations(nums, x) {
2
  let total = 0;
3
  for (const v of nums) total += v;
4
  if (total < x) return -1;
5

6
  // 两端删掉的元素之和 = x，等价于「中间留下的那一段，和 = total - x」；
7
  // 操作数最少 = 中间这一段最长
8
  const target = total - x;
9
  let sum = 0;
10
  let left = 0, right = 0, best = -1;
11

12
  while (right < nums.length) {
13
    sum += nums[right];              // ① 右边界入窗
14
    right++;
15

16
    while (sum > target) {           // ③ 都是正数，超了就能靠收缩降下来
17
      sum -= nums[left];
18
      left++;
19
    }
20
    if (sum === target && right - left > best)
21
      best = right - left;           // ④ 收缩后记录：这一段越长，操作数越少
22
  }
23
  return best < 0 ? -1 : nums.length - best;
24
}

1
#include <string.h>
2

3
int longestSubstring(char *s, int k) {
4
    int n = (int)strlen(s);
5
    int cnt[26], best = 0;
6

7
    for (int types = 1; types <= 26; types++) {   /* 枚举窗口里有几种字符 */
8
        memset(cnt, 0, sizeof(cnt));
9
        int left = 0, right = 0;
10
        int distinct = 0;      /* 窗口里有几种字符 */
11
        int reached = 0;       /* 其中有多少种的出现次数已经 ≥ k */
12

13
        while (right < n) {
14
            int c = s[right] - 'a';                /* ① 右边界入窗 */
15
            if (cnt[c]++ == 0) distinct++;
16
            if (cnt[c] == k) reached++;
17
            right++;
18

19
            while (distinct > types) {             /* ③ 种类超了就收缩 */
20
                int d = s[left] - 'a';
21
                if (cnt[d]-- == k) reached--;
22
                if (cnt[d] == 0) distinct--;
23
                left++;
24
            }
25
            if (distinct == types && reached == types && right - left > best)
26
                best = right - left;               /* ④ 窗口里每一种字符都 ≥ k 个 */
27
        }
28
    }
29
    return best;
30
}

1
function longestSubstring(s, k) {
2
  let best = 0;
3
  const cnt = new Array(26).fill(0);
4

5
  for (let types = 1; types <= 26; types++) {   // 枚举窗口里有几种字符
6
    cnt.fill(0);
7
    let left = 0, right = 0;
8
    let distinct = 0;    // 窗口里有几种字符
9
    let reached = 0;     // 其中有多少种的出现次数已经 ≥ k
10

11
    while (right < s.length) {
12
      const c = s.charCodeAt(right) - 97;       // ① 右边界入窗
13
      if (cnt[c]++ === 0) distinct++;
14
      if (cnt[c] === k) reached++;
15
      right++;
16

17
      while (distinct > types) {                // ③ 种类超了就收缩
18
        const d = s.charCodeAt(left) - 97;
19
        if (cnt[d]-- === k) reached--;
20
        if (cnt[d] === 0) distinct--;
21
        left++;
22
      }
23
      if (distinct === types && reached === types && right - left > best)
24
        best = right - left;                    // ④ 窗口里每一种字符都 ≥ k 个
25
    }
26
  }
27
  return best;
28
}