【LeetCode】170. Two Sum III – Data structure design

Difficulty:easy

Description

Design and implement a TwoSum class. It should support the following operations: add
and find.
add(input) – Add the number input to an internal data structure.
find(value) – Find if there exists any pair of numbers which sum is equal to the value.
For example,
add(1); add(3); add(5); find(4) -> true; find(7) -> false

Intuition

add(input): Use HashMap to store the input as key and its count as value.

find(value): similar to Two Sum

Solution

import java.util.HashMap;

import java.util.Map;

public class TwoSum {

	HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

	public void add(int input) {

		if (map.containsKey(input)) {

			map.put(input, map.get(input) + 1);

		} else

			map.put(input, 1);

	}

	public boolean find(int sum) {

		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {

			if (map.containsKey(sum - entry.getKey())) {

				if (entry.getKey() == sum - entry.getKey() && entry.getValue() == 1)

					return false;

				return true;

			}

		}

		return false;

	}

	public static void main(String[] args) {

		TwoSum a = new TwoSum();

		a.add(2);

		System.out.println(a.find(4)==false);

		a.add(2);

		a.add(6);

		System.out.println(a.find(4)==true);

		System.out.println(a.find(12)==false);

		System.out.println(a.find(8)==true);

		System.out.println(a.find(2)==false);

		a.add(10);

		System.out.println(a.find(12)==true);

	}

}

true

true

true

true

true

true

TwoSum

Complexity

Time complexity :

For Method add(): O(1)　

For Method find(): O(n) 　　(not O(1), because we need to iterate through the hashMap)

Space complexity :

O(n) for storage

What I've learned

1. Be aware of the duplicates when writing the method find().

2. How to iterate through an HashMap? Refer to 遍历HashMap

More:【目录】LeetCode Java实现

巴特西