LeetCode 981 时间键值存储（Time-Based Key-Value Store）全解法详解：暴力、有序映射与二分查找

LeetCode 981 时间键值存储（Time-Based Key-Value Store）全解法详解：暴力、有序映射与二分查找

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本篇指南以 articles/time-based-key-value-store.md 为骨架，围绕 LeetCode 981「基于时间的键值存储」问题展开：你需要设计一个数据结构TimeMap，支持set(key, value, timestamp)与get(key, timestamp)，其中get必须返回小于等于查询时刻的最新 value，找不到则返回空字符串。文章从暴力线性扫描讲起，逐步过渡到有序映射（Sorted Map）与数组二分查找两种O(log n)方案，并给出 Python、Java、C++、JavaScript、C#、Go、Kotlin、Swift、Rust 九种语言的完整实现；同时结合本仓库 python/0981-time-based-key-value-store.py、cpp/0981-time-based-key-value-store.cpp 等源码与 hints/time-based-key-value-store.md 提示，验证正确性并梳理边界陷阱。读完你将掌握「按时间查找 floor 值」这类问题的标准套路，以及哈希表 + 二分查找组合数据结构的工程化写法。

前置知识（Prerequisites）

在动手之前，你需要熟悉以下三块基础能力：

• 哈希表 / 字典（Hash maps/dictionaries）：以O(1)平均复杂度存储键值对并进行高效查找。本题的顶层容器必然是哈希表：key → 该键下的一组 (timestamp, value)。
• 二分查找（Binary search）：在有序数组中找到「小于等于查询值timestamp的最大时间戳」，时间复杂度O(log n)。这是本题从暴力法进化为高效解法的核心武器。
• 有序数据结构（Sorted data structures）：让每个 key 对应的时间戳保持有序，才能对get查询做二分。实现方式有两种：直接用语言内置的有序映射（如 Java 的TreeMap、C++ 的std::map），或利用题目「时间戳严格递增」的约束把数据追加进数组天然有序。

从本仓库的提示文件 hints/time-based-key-value-store.md 可以看到，期望的最优目标是：set()为O(1)时间、get()为O(log n)时间、空间为O(m * n)（其中n是某个 key 关联的 value 总数，m是 key 的总数）。

1. 暴力解法（Brute Force）

核心直觉

我们希望为每个 key 连同时间戳一起存下 value；当查询某个时刻的值时，返回在该时刻或之前最后一次设置的值。

暴力法的思路非常直接：原样存储一切，查询时把该 key 的所有时间戳扫一遍，挑出最匹配的那个。实现容易，但每次get()都要扫描全部时间戳，所以很慢。

算法步骤

1. 使用字典把每个 key 映射到一个「时间戳 → 值列表」的二级字典。
2. set(key, value, timestamp)：
   • 在对应时间戳下插入 value（同一时间戳可能多次set，因此用列表追加）。
3. get(key, timestamp)：
   • 若 key 不存在，返回空字符串""；
   • 否则遍历该 key 的全部时间戳；
   • 维护最大的time ≤ timestamp；
   • 返回该时间戳下存储的值。
4. 若不存在满足条件的时间戳，返回空字符串。

各语言实现

Python

class TimeMap: def __init__(self): self.keyStore = {} def set(self, key: str, value: str, timestamp: int) -> None: if key not in self.keyStore: self.keyStore[key] = {} if timestamp not in self.keyStore[key]: self.keyStore[key][timestamp] = [] self.keyStore[key][timestamp].append(value) def get(self, key: str, timestamp: int) -> str: if key not in self.keyStore: return "" seen = -1 for time in self.keyStore[key]: if time <= timestamp: seen = max(seen, time) return "" if seen == -1 else self.keyStore[key][seen][-1]

Java

public class TimeMap { private Map<String, Map<Integer, List<String>>> keyStore; public TimeMap() { keyStore = new HashMap<>(); } public void set(String key, String value, int timestamp) { if (!keyStore.containsKey(key)) { keyStore.put(key, new HashMap<>()); } if (!keyStore.get(key).containsKey(timestamp)) { keyStore.get(key).put(timestamp, new ArrayList<>()); } keyStore.get(key).get(timestamp).add(value); } public String get(String key, int timestamp) { if (!keyStore.containsKey(key)) { return ""; } int seen = -1; for (int time : keyStore.get(key).keySet()) { if (time <= timestamp) { seen = Math.max(seen, time); } } if (seen == -1) return ""; int back = keyStore.get(key).get(seen).size() - 1; return keyStore.get(key).get(seen).get(back); } }

C++

class TimeMap { public: unordered_map<string, unordered_map<int, vector<string>>> keyStore; TimeMap() {} void set(string key, string value, int timestamp) { keyStore[key][timestamp].push_back(value); } string get(string key, int timestamp) { if (keyStore.find(key) == keyStore.end()) { return ""; } int seen = -1; for (const auto& [time, _] : keyStore[key]) { if (time <= timestamp) { seen = max(seen, time); } } return seen == -1 ? "" : keyStore[key][seen].back(); } };

JavaScript

class TimeMap { constructor() { this.keyStore = new Map(); } /** * @param {string} key * @param {string} value * @param {number} timestamp * @return {void} */ set(key, value, timestamp) { if (!this.keyStore.has(key)) { this.keyStore.set(key, new Map()); } if (!this.keyStore.get(key).has(timestamp)) { this.keyStore.get(key).set(timestamp, []); } this.keyStore.get(key).get(timestamp).push(value); } /** * @param {string} key * @param {number} timestamp * @return {string} */ get(key, timestamp) { if (!this.keyStore.has(key)) { return ''; } let seen = -1; for (let time of this.keyStore.get(key).keys()) { if (time <= timestamp) { seen = Math.max(seen, time); } } return seen === -1 ? '' : this.keyStore.get(key).get(seen).at(-1); } }

C#

public class TimeMap { private Dictionary<string, Dictionary<int, List<string>>> keyStore; public TimeMap() { keyStore = new Dictionary<string, Dictionary<int, List<string>>>(); } public void Set(string key, string value, int timestamp) { if (!keyStore.ContainsKey(key)) { keyStore[key] = new Dictionary<int, List<string>>(); } if (!keyStore[key].ContainsKey(timestamp)) { keyStore[key][timestamp] = new List<string>(); } keyStore[key][timestamp].Add(value); } public string Get(string key, int timestamp) { if (!keyStore.ContainsKey(key)) { return ""; } var timestamps = keyStore[key]; int seen = -1; foreach (var time in timestamps.Keys) { if (time <= timestamp) { seen = Math.Max(seen, time); } } return seen == -1 ? "" : timestamps[seen][^1]; } }

Go

type TimeMap struct { keyStore map[string]map[int][]string } func Constructor() TimeMap { return TimeMap{ keyStore: make(map[string]map[int][]string), } } func (this *TimeMap) Set(key string, value string, timestamp int) { if _, exists := this.keyStore[key]; !exists { this.keyStore[key] = make(map[int][]string) } this.keyStore[key][timestamp] = append(this.keyStore[key][timestamp], value) } func (this *TimeMap) Get(key string, timestamp int) string { if _, exists := this.keyStore[key]; !exists { return "" } seen := -1 for time := range this.keyStore[key] { if time <= timestamp { seen = max(seen, time) } } if seen == -1 { return "" } values := this.keyStore[key][seen] return values[len(values)-1] } func max(a, b int) int { if a > b { return a } return b }

Kotlin

class TimeMap() { private val keyStore = HashMap<String, HashMap<Int, MutableList<String>>>() fun set(key: String, value: String, timestamp: Int) { if (!keyStore.containsKey(key)) { keyStore[key] = HashMap() } if (!keyStore[key]!!.containsKey(timestamp)) { keyStore[key]!![timestamp] = mutableListOf() } keyStore[key]!![timestamp]!!.add(value) } fun get(key: String, timestamp: Int): String { if (!keyStore.containsKey(key)) { return "" } var seen = -1 for (time in keyStore[key]!!.keys) { if (time <= timestamp) { seen = maxOf(seen, time) } } if (seen == -1) { return "" } return keyStore[key]!![seen]!!.last() } }

Swift

class TimeMap { private var keyStore: [String: [Int: [String]]] init() { self.keyStore = [:] } func set(_ key: String, _ value: String, _ timestamp: Int) { if keyStore[key] == nil { keyStore[key] = [:] } if keyStore[key]![timestamp] == nil { keyStore[key]![timestamp] = [] } keyStore[key]![timestamp]!.append(value) } func get(_ key: String, _ timestamp: Int) -> String { guard let timeMap = keyStore[key] else { return "" } var seen = -1 for time in timeMap.keys { if time <= timestamp { seen = max(seen, time) } } return seen == -1 ? "" : timeMap[seen]!.last! } }

Rust

struct TimeMap { key_store: HashMap<String, HashMap<i32, Vec<String>>>, } impl TimeMap { fn new() -> Self { TimeMap { key_store: HashMap::new(), } } fn set(&mut self, key: String, value: String, timestamp: i32) { self.key_store .entry(key) .or_default() .entry(timestamp) .or_default() .push(value); } fn get(&self, key: String, timestamp: i32) -> String { let Some(time_map) = self.key_store.get(&key) else { return String::new(); }; let mut seen = -1; for &time in time_map.keys() { if time <= timestamp && time > seen { seen = time; } } if seen == -1 { String::new() } else { time_map[&seen].last().unwrap().clone() } } }

复杂度分析

• 时间复杂度：set()为O(1)，get()为O(n)（需线性扫描该 key 的全部时间戳）。
• 空间复杂度：O(m * n)。

其中n是某个 key 关联的唯一时间戳总数，m是 key 的总数。

2. 二分查找：有序映射（Binary Search with Sorted Map）

核心直觉

对每个 key，我们按时间戳升序保存所有的(timestamp, value)对。

调用get(key, timestamp)时不再全量扫描，而是快速找到该 key 下最大的timestamp ≤ 查询时刻。由于时间戳有序，可以用二分查找在O(log n)内定位：

• 找到精确匹配，直接返回对应 value；
• 否则返回比查询时刻小且最接近的那个时间戳对应的 value；
• 若不存在更小或相等的时刻，返回""。

归纳起来就是：每个 key 维护有序时间戳 →get时二分搜索这些时间戳。

算法步骤

1. 维护映射：key → (timestamp, value) 的有序列表（或用两条平行数组分别存时间戳与 value）。
2. set(key, value, timestamp)：
   • 把(timestamp, value)插入该 key 的列表，保持时间戳有序；
   • （若时间戳始终按递增顺序到达，直接append即可）。
3. get(key, timestamp)：
   • 若 key 不存在，返回""；
   • 设times为该 key 的有序时间戳列表；
   • 在times上二分查找最右侧下标i满足times[i] ≤ timestamp；
   • 若存在，返回times[i]对应的 value；否则返回""（该时刻之前没有设置过值）。

各语言实现

Python（利用sortedcontainers.SortedDict的bisect_right）

from sortedcontainers import SortedDict class TimeMap: def __init__(self): self.m = defaultdict(SortedDict) def set(self, key: str, value: str, timestamp: int) -> None: self.m[key][timestamp] = value def get(self, key: str, timestamp: int) -> str: if key not in self.m: return "" timestamps = self.m[key] idx = timestamps.bisect_right(timestamp) - 1 if idx >= 0: closest_time = timestamps.iloc[idx] return timestamps[closest_time] return ""

Java（TreeMap.floorEntry天然就是 floor 查找）

public class TimeMap { private Map<String, TreeMap<Integer, String>> m; public TimeMap() { m = new HashMap<>(); } public void set(String key, String value, int timestamp) { m.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value); } public String get(String key, int timestamp) { if (!m.containsKey(key)) return ""; TreeMap<Integer, String> timestamps = m.get(key); Map.Entry<Integer, String> entry = timestamps.floorEntry(timestamp); return entry == null ? "" : entry.getValue(); } }

C++（std::map::upper_bound取前驱）

class TimeMap { public: unordered_map<string, map<int, string>> m; TimeMap() {} void set(string key, string value, int timestamp) { m[key].insert({timestamp, value}); } string get(string key, int timestamp) { auto it = m[key].upper_bound(timestamp); return it == m[key].begin() ? "" : prev(it)->second; } };

JavaScript（数组 + 手写二分）

class TimeMap { constructor() { this.keyStore = new Map(); } /** * @param {string} key * @param {string} value * @param {number} timestamp * @return {void} */ set(key, value, timestamp) { if (!this.keyStore.has(key)) { this.keyStore.set(key, []); } this.keyStore.get(key).push([timestamp, value]); } /** * @param {string} key * @param {number} timestamp * @return {string} */ get(key, timestamp) { const values = this.keyStore.get(key) || []; let left = 0; let right = values.length - 1; let result = ''; while (left <= right) { const mid = Math.floor((left + right) / 2); if (values[mid][0] <= timestamp) { result = values[mid][1]; left = mid + 1; } else { right = mid - 1; } } return result; } }

C#（SortedList+ 手写二分）

public class TimeMap { private Dictionary<string, SortedList<int, string>> m; public TimeMap() { m = new Dictionary<string, SortedList<int, string>>(); } public void Set(string key, string value, int timestamp) { if (!m.ContainsKey(key)) { m[key] = new SortedList<int, string>(); } m[key][timestamp] = value; } public string Get(string key, int timestamp) { if (!m.ContainsKey(key)) return ""; var timestamps = m[key]; int left = 0; int right = timestamps.Count - 1; while (left <= right) { int mid = left + (right - left) / 2; if (timestamps.Keys[mid] == timestamp) { return timestamps.Values[mid]; } else if (timestamps.Keys[mid] < timestamp) { left = mid + 1; } else { right = mid - 1; } } if (right >= 0) { return timestamps.Values[right]; } return ""; } }

Go（sort.Search找到第一个大于 timestamp 的位置）

type TimeMap struct { m map[string][]pair } type pair struct { timestamp int value string } func Constructor() TimeMap { return TimeMap{ m: make(map[string][]pair), } } func (this *TimeMap) Set(key string, value string, timestamp int) { this.m[key] = append(this.m[key], pair{timestamp, value}) } func (this *TimeMap) Get(key string, timestamp int) string { if _, exists := this.m[key]; !exists { return "" } pairs := this.m[key] idx := sort.Search(len(pairs), func(i int) bool { return pairs[i].timestamp > timestamp }) if idx == 0 { return "" } return pairs[idx-1].value }

Kotlin（TreeMap.floorEntry）

class TimeMap() { private val m = HashMap<String, TreeMap<Int, String>>() fun set(key: String, value: String, timestamp: Int) { m.computeIfAbsent(key) { TreeMap() }[timestamp] = value } fun get(key: String, timestamp: Int): String { if (!m.containsKey(key)) return "" return m[key]!!.floorEntry(timestamp)?.value ?: "" } }

Swift

class TimeMap { private var m: [String: [(Int, String)]] init() { self.m = [:] } func set(_ key: String, _ value: String, _ timestamp: Int) { if m[key] == nil { m[key] = [] } m[key]!.append((timestamp, value)) } func get(_ key: String, _ timestamp: Int) -> String { guard let timestamps = m[key] else { return "" } var l = 0, r = timestamps.count - 1 var res = "" while l <= r { let mid = (l + r) / 2 if timestamps[mid].0 <= timestamp { res = timestamps[mid].1 l = mid + 1 } else { r = mid - 1 } } return res } }

Rust（partition_point返回第一个不满足条件的位置）

struct TimeMap { m: HashMap<String, Vec<(i32, String)>>, } impl TimeMap { fn new() -> Self { TimeMap { m: HashMap::new() } } fn set(&mut self, key: String, value: String, timestamp: i32) { self.m.entry(key).or_default().push((timestamp, value)); } fn get(&self, key: String, timestamp: i32) -> String { let Some(pairs) = self.m.get(&key) else { return String::new(); }; let idx = pairs.partition_point(|p| p.0 <= timestamp); if idx == 0 { String::new() } else { pairs[idx - 1].1.clone() } } }

复杂度分析

• 时间复杂度：set()视语言为O(n)或O(log n)（平衡树插入 / 有序容器维护），get()为O(log n)。
• 空间复杂度：O(m * n)。

其中n是某个 key 关联的 value 总数，m是 key 的总数。

3. 二分查找：数组方案（Binary Search with Array）

核心直觉

每个 key 按插入顺序保存 value，而题目保证每个 key 的时间戳严格递增。因此我们只需为每个 key 维护一个简单的(value, timestamp)列表即可。

回答get(key, timestamp)时，只需要找到最大的 ≤ 查询时刻的时间戳。因为时间戳天然有序，二分查找可以快速定位，无需全量扫描。

这是一种既高效又简洁的做法：value 存数组，查询时对时间戳二分。

算法步骤

1. 使用字典：key → [value, timestamp] 列表；每个 key 的时间戳按序存储（因为它们递增到达）。
2. set(key, value, timestamp)：
   • 把[value, timestamp]追加到该 key 的列表末尾。
3. get(key, timestamp)：
   • 若 key 不存在，返回""；
   • 设arr为[value, timestamp]对列表；
   • 对时间戳二分，找到最右侧的t ≤ timestamp；
   • 找到则返回对应 value，否则返回""。

各语言实现

Python

class TimeMap: def __init__(self): self.keyStore = {} # key : list of [val, timestamp] def set(self, key: str, value: str, timestamp: int) -> None: if key not in self.keyStore: self.keyStore[key] = [] self.keyStore[key].append([value, timestamp]) def get(self, key: str, timestamp: int) -> str: res, values = "", self.keyStore.get(key, []) l, r = 0, len(values) - 1 while l <= r: m = (l + r) // 2 if values[m][1] <= timestamp: res = values[m][0] l = m + 1 else: r = m - 1 return res

Java

public class TimeMap { private Map<String, List<Pair<Integer, String>>> keyStore; public TimeMap() { keyStore = new HashMap<>(); } public void set(String key, String value, int timestamp) { keyStore.computeIfAbsent(key, k -> new ArrayList<>()).add(new Pair<>(timestamp, value)); } public String get(String key, int timestamp) { List<Pair<Integer, String>> values = keyStore.getOrDefault(key, new ArrayList<>()); int left = 0, right = values.size() - 1; String result = ""; while (left <= right) { int mid = left + (right - left) / 2; if (values.get(mid).getKey() <= timestamp) { result = values.get(mid).getValue(); left = mid + 1; } else { right = mid - 1; } } return result; } private static class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this.key = key; this.value = value; } public K getKey() { return key; } public V getValue() { return value; } } }

C++

class TimeMap { private: unordered_map<string, vector<pair<int, string>>> keyStore; public: TimeMap() {} void set(string key, string value, int timestamp) { keyStore[key].emplace_back(timestamp, value); } string get(string key, int timestamp) { auto& values = keyStore[key]; int left = 0, right = values.size() - 1; string result = ""; while (left <= right) { int mid = left + (right - left) / 2; if (values[mid].first <= timestamp) { result = values[mid].second; left = mid + 1; } else { right = mid - 1; } } return result; } };

JavaScript

class TimeMap { constructor() { this.keyStore = new Map(); } /** * @param {string} key * @param {string} value * @param {number} timestamp * @return {void} */ set(key, value, timestamp) { if (!this.keyStore.has(key)) { this.keyStore.set(key, []); } this.keyStore.get(key).push([timestamp, value]); } /** * @param {string} key * @param {number} timestamp * @return {string} */ get(key, timestamp) { const values = this.keyStore.get(key) || []; let left = 0; let right = values.length - 1; let result = ''; while (left <= right) { const mid = Math.floor((left + right) / 2); if (values[mid][0] <= timestamp) { result = values[mid][1]; left = mid + 1; } else { right = mid - 1; } } return result; } }

C#

public class TimeMap { private Dictionary<string, List<Tuple<int, string>>> keyStore; public TimeMap() { keyStore = new Dictionary<string, List<Tuple<int, string>>>(); } public void Set(string key, string value, int timestamp) { if (!keyStore.ContainsKey(key)) { keyStore[key] = new List<Tuple<int, string>>(); } keyStore[key].Add(Tuple.Create(timestamp, value)); } public string Get(string key, int timestamp) { if (!keyStore.ContainsKey(key)) { return ""; } var values = keyStore[key]; int left = 0, right = values.Count - 1; string result = ""; while (left <= right) { int mid = left + (right - left) / 2; if (values[mid].Item1 <= timestamp) { result = values[mid].Item2; left = mid + 1; } else { right = mid - 1; } } return result; } }

Go

type TimeMap struct { m map[string][]pair } type pair struct { timestamp int value string } func Constructor() TimeMap { return TimeMap{ m: make(map[string][]pair), } } func (this *TimeMap) Set(key string, value string, timestamp int) { this.m[key] = append(this.m[key], pair{timestamp, value}) } func (this *TimeMap) Get(key string, timestamp int) string { if _, exists := this.m[key]; !exists { return "" } pairs := this.m[key] l, r := 0, len(pairs)-1 for l <= r { mid := (l + r) / 2 if pairs[mid].timestamp <= timestamp { if mid == len(pairs)-1 || pairs[mid+1].timestamp > timestamp { return pairs[mid].value } l = mid + 1 } else { r = mid - 1 } } return "" }

Kotlin

class TimeMap() { private val keyStore = HashMap<String, MutableList<Pair<String, Int>>>() fun set(key: String, value: String, timestamp: Int) { if (!keyStore.containsKey(key)) { keyStore[key] = mutableListOf() } keyStore[key]!!.add(Pair(value, timestamp)) } fun get(key: String, timestamp: Int): String { var res = "" val values = keyStore[key] ?: return res var l = 0 var r = values.size - 1 while (l <= r) { val m = (l + r) / 2 if (values[m].second <= timestamp) { res = values[m].first l = m + 1 } else { r = m - 1 } } return res } }

Swift

class TimeMap { private var keyStore: [String: [(String, Int)]] init() { self.keyStore = [:] } func set(_ key: String, _ value: String, _ timestamp: Int) { if keyStore[key] == nil { keyStore[key] = [] } keyStore[key]!.append((value, timestamp)) } func get(_ key: String, _ timestamp: Int) -> String { guard let values = keyStore[key] else { return "" } var res = "" var l = 0, r = values.count - 1 while l <= r { let m = (l + r) / 2 if values[m].1 <= timestamp { res = values[m].0 l = m + 1 } else { r = m - 1 } } return res } }

Rust

struct TimeMap { key_store: HashMap<String, Vec<(String, i32)>>, } impl TimeMap { fn new() -> Self { TimeMap { key_store: HashMap::new(), } } fn set(&mut self, key: String, value: String, timestamp: i32) { self.key_store.entry(key).or_default().push((value, timestamp)); } fn get(&self, key: String, timestamp: i32) -> String { let Some(values) = self.key_store.get(&key) else { return String::new(); }; let mut res = String::new(); let (mut l, mut r) = (0i32, values.len() as i32 - 1); while l <= r { let m = (l + r) / 2; if values[m as usize].1 <= timestamp { res = values[m as usize].0.clone(); l = m + 1; } else { r = m - 1; } } res } }

复杂度分析

• 时间复杂度：set()为O(1)（纯追加），get()为O(log n)（二分查找）。
• 空间复杂度：O(m * n)。

其中n是某个 key 关联的 value 总数，m是 key 的总数。

仓库源码验证：数组二分方案是各语言提交的主流实现

上述三种方案中，方案三（数组 + 二分）在工程上最干净：set是纯追加、get是标准「找 floor」二分，且完全依赖题目「时间戳严格递增」的保证。本仓库中绝大多数语言的提交正是这一方案，可以直接对照验证：

• python/0981-time-based-key-value-store.py：keyStore[key].append([value, timestamp])，get内while l <= r二分并持续记录res，是 Python 版本的标准写法。
• java/0981-time-based-key-value-store.java：使用HashMap<String, List<Pair<String, Integer>>>，并把二分抽成独立的search方法，采用上取中（start + (end - start + 1) / 2）配合start = mid收缩区间的写法，最后在循环外统一校验list.get(start).getValue() <= timestamp，与原文的「先置result再右移left」等价。
• cpp/0981-time-based-key-value-store.cpp：unordered_map<string, vector<pair<int, string>>>，二分到精确命中立即返回，未命中时high >= 0说明m[key][high]是最后一个≤ timestamp的 pair——文件头注释也明确点出「timestamps are naturally in order, binary search」的设计动机。
• go/0981-time-based-key-value-store.go：用ValStamp{Val, Time}结构体切片存储，二分命中时额外判断mid == len(pairs)-1 || pairs[mid+1].timestamp > timestamp以确保取到的是最后一个满足条件的值。
• rust/0981-time-based-key-value-store.rs：HashMap<String, Vec<(String, i32)>>，采用左闭右开区间[0, len)二分，timestamp < t_list[m].1时收缩右界，否则记录res并右移左界。
• 其余语言可继续参考：javascript/0981-time-based-key-value-store.js、typescript/0981-time-based-key-value-store.ts、csharp/0981-time-based-key-value-store.cs、kotlin/0981-time-based-key-value-store.kt、swift/0981-time-based-key-value-store.swift、ruby/0981-time-based-key-value-store.rb，以及 C 语言的 c/0981-time-based-key-value-store.c。

另外，hints/time-based-key-value-store.md 给出的四条提示与本文的推导路径一致：先用哈希表存「key → (value, timestamp) 列表」保证set为O(1)；暴力get是线性扫描；由于时间戳天然升序，最终用二分查找定位「最接近且不超过查询时刻」的时间戳。

常见陷阱（Common Pitfalls）

陷阱一：用精确匹配代替 floor 查找

常见错误是只搜索「恰好等于查询时刻」的时间戳，而不是找小于等于查询时刻的最大时间戳。二分应定位满足timestamp <= query的最右侧值，而非精确命中。如果不存在精确匹配但存在更早的时间戳，此时返回空字符串就是错误的——应该返回最近一次更早时刻设置的值。

陷阱二：二分边界的 off-by-one 错误

二分边界极易出错。比如 Python 中误用bisect_left代替bisect_right，或搜索结束后没有正确调整下标，都会导致返回时间戳大于查询时刻的值。务必通过边界用例验证你的二分返回的是正确的 floor 值，例如：

• 在任意set之前就发起get（此时应返回空字符串）；
• 查询时刻恰好等于某个已存储的时间戳（应返回该时间戳的值）；
• 查询时刻介于两个相邻时间戳之间（应返回左侧较小时间戳的值）。

陷阱三：key 存在但时间戳过早时返回错误结果

当 key 存在、但该 key 下所有时间戳都大于查询时刻时，正确行为是返回空字符串。有些实现会错误地返回最早存储的那个值。一定要在取值前检查找到的下标是否有效（非负），例如方案一中的seen == -1判断、方案三中的idx == 0与result == ""哨兵值，都是为了防止这类越界取值的错误。

三种方案对比总结

选择建议：在 LeetCode 981 的约束（同一 key 的时间戳严格递增）下，方案三是面试中最推荐的写法——set达到最优的O(1)，get达到O(log n)，代码结构清晰、易于证明正确性；方案二则适用于时间戳可能乱序到达的变体场景，可以视作该题的通用化版本。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode