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

Posted on | In
Words count in article: 288 | Reading time ≈ 1

题目

设计并实现一个 TwoSum 的类，使该类需要支持 add 和 find 的操作。

add 操作 - 对内部数据结构增加一个数。
find 操作 - 寻找内部数据结构中是否存在一对整数，使得两数之和与给定的数相等。

示例1

1
2
3
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

示例2：

1
2
3
add(3); add(1); add(2);
find(3) -> true
find(6) -> false

解法

解法一：

使用HashMap保存元素出现的次数。

如果target刚好是其中某个值的两倍，那么该值的出现次数一定要大于等于2

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class TwoSum {
	private HashMap<Integer, Integer> numCounts;

	/** Initialize your data structure here. */
	public TwoSum() {
		this.numCounts = new HashMap<Integer, Integer>();
	}

	/** Add the number to an internal data structure.. */
	public void add(int number) {
		if (this.numCounts.containsKey(number)) {
			this.numCounts.replace(number, this.numCounts.get(number) + 1);
		} else {
			this.numCounts.put(number, 1);
		}
	}

	/**
	 * Find if there exists any pair of numbers which sum is equal to the value.
	 */
	public boolean find(int value) {
		for (Map.Entry<Integer, Integer> entry : this.numCounts.entrySet()) {
			int complement = value - entry.getKey();
			if (complement != entry.getKey()) {
				if (this.numCounts.containsKey(complement)) {
					return true;
				}
			} else {
				if (entry.getValue() > 1) {
					return true;
				}
			}
		}
		return false;
	}
}

0%