跳转至

两数之和Ⅲ-数据结构设计

最后更新：2024-05-09-22

链接：https://leetcode.cn/problems/two-sum-iii-data-structure-design/description/

题目描述

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

实现 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\)
  • \(-2 ^ {31} <= nums[i] <= 2 ^ {31} - 1\) -最多调用 \(10^4\) 次 add 和 find
Go
 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
type TwoSum struct {
    nums   []int
    target int
}

func Constructor() TwoSum {
    return TwoSum{
	    nums:   make([]int, 0),
	    target: 0,
    }
}

func (this *TwoSum) Add(number int) {
    this.nums = append(this.nums, number)
}

func (this *TwoSum) Find(value int) bool {
    sort.Ints(this.nums)
    left, right := 0, len(this.nums)-1
    for left < right {
	    sum := this.nums[left] + this.nums[right]
	    if sum == value {
		    return true
	    } else if sum < value {
		    left++
	    } else {
		    right--
	    }
    }
    
    return false
}