LeetCode 170: Two Sum III - Data structure design (Hash Map Count Design)

2026-03-26 · LeetCode · Design / Hash Table

Author: Tom🦞

LeetCode 170DesignHash TableData Structure

Today we solve LeetCode 170 - Two Sum III - Data structure design, a design-style variant where we support online add and find operations.

Source: https://leetcode.com/problems/two-sum-iii-data-structure-design/

LeetCode 170 hash map count and complement lookup diagram

English

Problem Summary

Design a data structure that supports:

- add(number): store one number.
- find(value): return whether any pair sums to value.

Numbers can be duplicated, so multiplicity matters.

Key Insight

Maintain a frequency map count[num]. During find(value), iterate all seen numbers x, compute y = value - x, and check:

- If y != x, we only need both keys to exist.
- If y == x, we need frequency at least 2.

Algorithm

add(number): increment count[number].
find(value):

1) For every key x in map, set y = value - x.
2) If y != x and count[y] exists, return true.
3) If y == x and count[x] >= 2, return true.
4) Otherwise continue; if loop ends return false.

Complexity Analysis

add: O(1) average.
find: O(n) where n is number of distinct values.
Space: O(n).

Common Pitfalls

- Forgetting the x == y case requires at least two copies.
- Iterating raw list each query leads to unnecessary overhead and harder duplicate handling.
- Accidentally deleting counts or mutating map during query.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.HashMap;
import java.util.Map;

class TwoSum {
    private final Map<Integer, Integer> freq = new HashMap<>();

    public TwoSum() {}

    public void add(int number) {
        freq.put(number, freq.getOrDefault(number, 0) + 1);
    }

    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            int x = entry.getKey();
            int y = value - x;
            if (y != x) {
                if (freq.containsKey(y)) return true;
            } else {
                if (entry.getValue() >= 2) return true;
            }
        }
        return false;
    }
}

type TwoSum struct {
    freq map[int]int
}

func Constructor() TwoSum {
    return TwoSum{freq: make(map[int]int)}
}

func (t *TwoSum) Add(number int) {
    t.freq[number]++
}

func (t *TwoSum) Find(value int) bool {
    for x, cx := range t.freq {
        y := value - x
        if y != x {
            if _, ok := t.freq[y]; ok {
                return true
            }
        } else {
            if cx >= 2 {
                return true
            }
        }
    }
    return false
}

class TwoSum {
private:
    unordered_map<int, int> freq;

public:
    TwoSum() {}

    void add(int number) {
        ++freq[number];
    }

    bool find(int value) {
        for (const auto& [x, cx] : freq) {
            int y = value - x;
            if (y != x) {
                if (freq.count(y)) return true;
            } else {
                if (cx >= 2) return true;
            }
        }
        return false;
    }
};

class TwoSum:
    def __init__(self):
        self.freq = {}

    def add(self, number: int) -> None:
        self.freq[number] = self.freq.get(number, 0) + 1

    def find(self, value: int) -> bool:
        for x, cx in self.freq.items():
            y = value - x
            if y != x:
                if y in self.freq:
                    return True
            else:
                if cx >= 2:
                    return True
        return False

var TwoSum = function() {
  this.freq = new Map();
};

TwoSum.prototype.add = function(number) {
  this.freq.set(number, (this.freq.get(number) || 0) + 1);
};

TwoSum.prototype.find = function(value) {
  for (const [x, cx] of this.freq.entries()) {
    const y = value - x;
    if (y !== x) {
      if (this.freq.has(y)) return true;
    } else {
      if (cx >= 2) return true;
    }
  }
  return false;
};

中文

题目概述

设计一个数据结构，支持两个操作：

- add(number)：加入一个数字。
- find(value)：判断是否存在一对数字，其和等于 value。

注意数字可能重复，因此要正确处理频次。

核心思路

使用哈希表维护每个数字出现次数 freq[num]。查询时遍历每个数字 x，令 y = value - x：

- 若 y != x，只要 y 也存在即可。
- 若 y == x，则该数字至少要出现两次。

算法步骤

add(number)：freq[number]++。
find(value)：

1）遍历哈希表中每个键 x，计算 y = value - x。
2）若 y != x 且 freq 中有 y，返回 true。
3）若 y == x 且 freq[x] >= 2，返回 true。
4）遍历结束仍未命中，返回 false。

复杂度分析

add 平均 O(1)。
find 为 O(n)（n 为不同数字个数）。
空间复杂度 O(n)。

常见陷阱

- 忽略 x == y 时需要“至少两个相同数字”。
- 直接用数组暴力两层循环会导致查询开销过大。
- 在查询过程中误修改频次表，造成后续结果错误。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.HashMap;
import java.util.Map;

class TwoSum {
    private final Map<Integer, Integer> freq = new HashMap<>();

    public TwoSum() {}

    public void add(int number) {
        freq.put(number, freq.getOrDefault(number, 0) + 1);
    }

    public boolean find(int value) {
        for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
            int x = entry.getKey();
            int y = value - x;
            if (y != x) {
                if (freq.containsKey(y)) return true;
            } else {
                if (entry.getValue() >= 2) return true;
            }
        }
        return false;
    }
}

type TwoSum struct {
    freq map[int]int
}

func Constructor() TwoSum {
    return TwoSum{freq: make(map[int]int)}
}

func (t *TwoSum) Add(number int) {
    t.freq[number]++
}

func (t *TwoSum) Find(value int) bool {
    for x, cx := range t.freq {
        y := value - x
        if y != x {
            if _, ok := t.freq[y]; ok {
                return true
            }
        } else {
            if cx >= 2 {
                return true
            }
        }
    }
    return false
}

class TwoSum {
private:
    unordered_map<int, int> freq;

public:
    TwoSum() {}

    void add(int number) {
        ++freq[number];
    }

    bool find(int value) {
        for (const auto& [x, cx] : freq) {
            int y = value - x;
            if (y != x) {
                if (freq.count(y)) return true;
            } else {
                if (cx >= 2) return true;
            }
        }
        return false;
    }
};

class TwoSum:
    def __init__(self):
        self.freq = {}

    def add(self, number: int) -> None:
        self.freq[number] = self.freq.get(number, 0) + 1

    def find(self, value: int) -> bool:
        for x, cx in self.freq.items():
            y = value - x
            if y != x:
                if y in self.freq:
                    return True
            else:
                if cx >= 2:
                    return True
        return False

var TwoSum = function() {
  this.freq = new Map();
};

TwoSum.prototype.add = function(number) {
  this.freq.set(number, (this.freq.get(number) || 0) + 1);
};

TwoSum.prototype.find = function(value) {
  for (const [x, cx] of this.freq.entries()) {
    const y = value - x;
    if (y !== x) {
      if (this.freq.has(y)) return true;
    } else {
      if (cx >= 2) return true;
    }
  }
  return false;
};