列表

详情


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

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

实现 TwoSum 类:

 

示例:

输入:
["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

 

提示:

相似题目

两数之和

单词的唯一缩写

两数之和 IV - 输入二叉搜索树

原站题解

去查看

上次编辑到这里,代码来自缓存 点击恢复默认模板
class TwoSum { public: TwoSum() { } void add(int number) { } bool find(int value) { } }; /** * Your TwoSum object will be instantiated and called as such: * TwoSum* obj = new TwoSum(); * obj->add(number); * bool param_2 = obj->find(value); */

java 解法, 执行用时: 88 ms, 内存消耗: 49.2 MB, 提交时间: 2023-10-15 19:36:39

class TwoSum {

    private Set<Integer> all;
    private Set<Integer> duplicate;
    
    /** Initialize your data structure here. */
    public TwoSum() {
        all = new HashSet();
        duplicate = new HashSet();
    }
    
    /** Add the number to an internal data structure.. */
    public void add(int number) {
        if (all.contains(number))
            duplicate.add(number);
        else
            all.add(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        int target;
        for (int num: all) {
            target = value - num;
            if (target == num && duplicate.contains(target))
                return true;
            if (target != num && all.contains(target))
                return true;
        }
        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */

cpp 解法, 执行用时: 156 ms, 内存消耗: 28.1 MB, 提交时间: 2023-10-15 19:36:16

class TwoSum {
public:
    unordered_map<long long,int> dic;

    /** Initialize your data structure here. */
    TwoSum() 
    {

    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) 
    {
        if (dic.count(number) != 0)
            dic[number] ++;
        else
            dic[number] = 1;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) 
    {
        for (auto [x, freq]: dic)
        {
            long long y = (long long)value - x;
            if (x == y)
            {
                if (dic[x] >= 2)
                    return true;
            }
            else
            {
                if (dic.count(y) != 0)
                {
                    return true;
                }
            }
        }
        return false;
    }
};



/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */

python3 解法, 执行用时: 304 ms, 内存消耗: 21.4 MB, 提交时间: 2023-10-15 19:35:53

class TwoSum:

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.dic = defaultdict(int)


    def add(self, number: int) -> None:
        """
        Add the number to an internal data structure..
        """
        self.dic[number] += 1

    def find(self, value: int) -> bool:
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        """
        for x in self.dic.keys():
            y = value - x
            if x == y:
                if self.dic[x] >= 2:
                    return True
            else:
                if y in self.dic:
                    return True
        return False


# Your TwoSum object will be instantiated and called as such:
# obj = TwoSum()
# obj.add(number)
# param_2 = obj.find(value)

golang 解法, 执行用时: 28 ms, 内存消耗: 7.4 MB, 提交时间: 2023-10-15 19:35:31

type TwoSum struct {
    val map[int]int
    max int64
    min int64
}


/** Initialize your data structure here. */
func Constructor() TwoSum {

    val :=  make(map[int]int)
    return TwoSum{val:val,min:math.MaxInt64,max:math.MinInt64}

}


/** Add the number to an internal data structure.. */
func (this *TwoSum) Add(number int)  {

    this.min= min(this.min,int64(number))
    this.max= max(this.max,int64(number))
    this.val[number]++
}


/** Find if there exists any pair of numbers which sum is equal to the value. */
func (this *TwoSum) Find(value int) bool {

    if int64(value) < this.min +this.min || int64(value) > this.max+this.max {
        return false
    }
    for k,v:=range this.val {
        if value -k == k   {
            if v > 1 {
                return true
            }
            
        } else {
            if this.val[value-k] > 0 {
                return true
            }            
        }
    }
    return false
}


func max(a, b int64) int64 {
    if a >b {
        return a
    }
    return  b
}


func min(a,b int64) int64 {
    if a < b {
        return a
    }
    return b
}


/**
 * Your TwoSum object will be instantiated and called as such:
 * obj := Constructor();
 * obj.Add(number);
 * param_2 := obj.Find(value);
 */

上一题