170. 两数之和 III - 数据结构设计 🔒

🟢   🔖  设计 数组 哈希表 双指针 数据流  🔗 力扣 LeetCode

题目

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

• TwoSum() Initializes the TwoSum object, with an empty array initially.
• void add(int number) Adds number to the data structure.
• boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.

Example 1:

Input

["TwoSum", "add", "add", "add", "find", "find"]

[[], [1], [3], [5], [4], [7]]

Output

[null, null, null, null, true, false]

Explanation

TwoSum twoSum = new TwoSum();

twoSum.add(1); // [] --> [1]

twoSum.add(3); // [1] --> [1,3]

twoSum.add(5); // [1,3] --> [1,3,5]

twoSum.find(4); // 1 + 3 = 4, return true

twoSum.find(7); // No two integers sum up to 7, return false

Constraints:

• -10^5 <= number <= 10^5
• -231 <= value <= 231 - 1
• At most 10^4 calls will be made to add and find.

题目大意

设计一个接收整数流的数据结构，该数据结构支持检查是否存在两数之和等于特定值。

实现 TwoSum 类：

• TwoSum() 使用空数组初始化 TwoSum 对象
• void add(int number) 向数据结构添加一个数 number
• boolean find(int value) 寻找数据结构中是否存在一对整数，使得两数之和与给定的值相等。如果存在，返回 true ；否则，返回 false 。

示例：

输入：

["TwoSum", "add", "add", "add", "find", "find"]

[[], [1], [3], [5], [4], [7]]

输出：

[null, null, null, null, true, false]

解释：

TwoSum twoSum = new TwoSum();

twoSum.add(1); // [] --> [1]

twoSum.add(3); // [1] --> [1,3]

twoSum.add(5); // [1,3] --> [1,3,5]

twoSum.find(4); // 1 + 3 = 4，返回 true

twoSum.find(7); // 没有两个整数加起来等于 7 ，返回 false

提示：

• -10^5 <= number <= 10^5
• -231 <= value <= 231 - 1
• 最多调用 10^4 次 add 和 find

解题思路

思路一：哈希表

1. 使用一个哈希表 map 来存储每个数字出现的次数。
2. 对于 find(value) 操作：
   • 遍历哈希表中的每个键 key，检查是否存在 value - key：
     • 如果 key 和 value - key 不同，直接检查是否存在 value - key。
     • 如果 key 和 value - key 相同，确保其出现次数大于 1。

复杂度分析

• 时间复杂度：
  • add(number)：O(1)（哈希表插入）。
  • find(value)：O(k)，其中 k 是哈希表中存储的不同数字的数量。
• 空间复杂度：O(k)，使用哈希表存储不同数字的数量。

若频繁调用 add(number)，推荐使用 哈希表解法，因其插入高效。

---

思路二：排序 + 双指针

1. 使用一个数组 list 来存储所有插入的数字，同时维护其有序性。
2. 对于 find(value) 操作，使用双指针法：
   • 左指针从开头，右指针从末尾。
   • 如果两数和小于目标值，左指针右移；如果大于目标值，右指针左移；如果等于目标值，返回 true。

复杂度分析

• 时间复杂度：
  • add(number)：O(n)，二分查找插入位置 O(log n)，插入元素O(n)。
  • find(value)：O(n)，双指针遍历数组。
• 空间复杂度：O(n)，使用有序数组存储所有插入的数字。

---

思路三：预计算所有两数之和

1. 直接存储所有可能的两数之和（以空间换时间）。
2. 使用一个哈希集合 sums 来存储两数之和。
3. 对于 add(number) 操作：遍历已有的所有数字，将 number 和它们的和加入到 sums 中。
4. 对于 find(value) 操作：直接检查 sums 是否包含 value。

复杂度分析

• 时间复杂度：
  • add(number)：O(n)，其中 n 是当前已添加的数字数量。
  • find(value)：O(1)。
• 空间复杂度：O(n^2)，在最坏情况下，Set 中可能存储了 n * (n - 1) / 2 个和。

若频繁调用 find(value)，推荐使用 预计算解法，因其查询效率高。但此解法在数据规模较大时可能不适用，因为 sums 会快速膨胀，占用大量内存。

代码

哈希表

class TwoSum {
	constructor() {
		this.map = new Map();
	}

	add(number) {
		this.map.set(number, (this.map.get(number) || 0) + 1);
	}

	find(value) {
		for (let key of this.map.keys()) {
			const complement = value - key;
			if (
				(complement !== key && this.map.has(complement)) ||
				(complement === key && this.map.get(key) > 1)
			) {
				return true;
			}
		}
		return false;
	}
}

排序 + 双指针

class TwoSum {
	constructor() {
		this.list = [];
	}

	add(number) {
		let pos = this.binaryInsertPosition(number);
		this.list.splice(pos, 0, number); // 插入保持有序
	}

	find(value) {
		let left = 0,
			right = this.list.length - 1;
		while (left < right) {
			const sum = this.list[left] + this.list[right];
			if (sum === value) {
				return true;
			} else if (sum < value) {
				left++;
			} else {
				right--;
			}
		}
		return false;
	}

	binaryInsertPosition(target) {
		let left = 0,
			right = this.list.length;
		while (left < right) {
			const mid = Math.floor((left + right) / 2);
			if (this.list[mid] < target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return left;
	}
}

预计算所有两数之和

class TwoSum {
	constructor() {
		this.nums = [];
		this.sums = new Set();
	}

	add(number) {
		for (let num of this.nums) {
			this.sums.add(num + number);
		}
		this.nums.push(number);
	}

	find(value) {
		return this.sums.has(value);
	}
}