Question

Formatted question description: https://leetcode.ca/all/170.html

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⁵ <= number <= 10⁵
-2³¹ <= value <= 2³¹ - 1
At most 10⁴ calls will be made to add and find.

Algorithm

HashMap to hold remainder.

Establish a mapping between each number and the number of occurrences, and then traverse the HashMap. For each value, first find the difference t between this value and the target value, and then you need to look at it in two cases.

If the current value is not equal to the difference t, then return True as long as there is a difference t in the HashMap, or when the difference t is equal to the current value,
If the number of mapping times of the HashMap is greater than 1, it means that there is another number in the HashMap that is equal to the current value, and the addition of the two is the target value

Code

// time: O(N)
// space: O(N)
public class TwoSum {

    // number to frequency
    private HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();

    public void add(int number) {
        if (hm.containsKey(number)) {
            hm.put(number, hm.get(number) + 1);
        } else {
            hm.put(number, 1);
        }
    }

    public boolean find(int value) {
        for (Integer oneNumber : hm.keySet()) {
            int target = value - oneNumber;
            if (hm.containsKey(target)) {
                // @note: for case: add=3, add=3, target=6
                if (oneNumber == target && hm.get(target) < 2) {
                    continue;
                }
                return true;
            }
        }
        return false;
    }
}

###############

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

    public TwoSum() {
    }

    public void add(int number) {
        cnt.merge(number, 1, Integer::sum);
    }

    public boolean find(int value) {
        for (var e : cnt.entrySet()) {
            int x = e.getKey(), v = e.getValue();
            int y = value - x;
            if (cnt.containsKey(y)) {
                if (x != y || v > 1) {
                    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);
 */

// OJ: https://leetcode.com/problems/two-sum-iii-data-structure-design/
// Time:
//      TwoSum: O(1)
//      add: O(logN)
//      find: O(NlogN)
// Space: O(N)
class TwoSum {
    map<long, int> m;
public:
    TwoSum() {}
    void add(int n) {
        m[n]++;
    }
    bool find(int n) {
        for (auto &[a, cnt] : m) {
            long b = n - a;
            if (a > b) return false;
            if (a == b) return cnt > 1;
            if (m.count(b)) return true;
        }
        return false;
    }
};

class TwoSum:
    def __init__(self):
        self.cnt = Counter()

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

    def find(self, value: int) -> bool:
        for x, v in self.cnt.items():
            y = value - x
            if y in self.cnt:
                # v > 1, for case: add=3, add=3, target=6
                if x != y or v > 1:
                    return True
        return False


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

############

class TwoSum(object):

  def __init__(self):
    """
    initialize your data structure here
    """
    self.nums = {}

  def add(self, number):
    """
    Add the number to an internal data structure.
    :rtype: nothing
    """
    self.nums[number] = self.nums.get(number, 0) + 1

  def find(self, value):
    """
    Find if there exists any pair of numbers which sum is equal to the value.
    :type value: int
    :rtype: bool
    """
    d = self.nums
    for num in d:
      t = value - num
      if t in d:
        if t == num:
          if d[t] >= 2:
            return True
        else:
          return True

    return False

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

type TwoSum struct {
	cnt map[int]int
}

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

func (this *TwoSum) Add(number int) {
	this.cnt[number]++
}

func (this *TwoSum) Find(value int) bool {
	for x, v := range this.cnt {
		y := value - x
		if _, ok := this.cnt[y]; ok && (x != y || v > 1) {
			return true
		}
	}
	return false
}

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

170 - Two Sum III - Data structure design

Question

Algorithm

Code

All Problems

All Solutions

Welcome to Subscribe On Youtube

Question

Algorithm

Code

All Problems

All Solutions