170. Two Sum III - Data structure design

  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
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108

/*
 * 170. Two Sum III - Data structure design My Submissions QuestionEditorial Solution
Total Accepted: 13104 Total Submissions: 55431 Difficulty: Easy
Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.
find - 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
Hide Company Tags LinkedIn
Hide Tags Hash Table Design
Show Similar Problems

 */
package ood;

import java.util.*;

public class TwoSumDesign{

	HashMap<Integer, Integer> map = new HashMap<>(); //记录数字和它出现的次数
	List<Integer> nums = new ArrayList<>();  // 记录添加的元素
	// https://discuss.leetcode.com/topic/32786/beats-100-java-code

	// Add the number to an internal data structure.
	public void add(int number) {
		if (map.containsKey(number)) {
			map.put(number, map.get(number) + 1);
		} else {
			map.put(number, 1);
			nums.add(number);
		}
	}

	// Find if there exists any pair of numbers which sum is equal to the value.
	public boolean find(int value) {

		for (int i = 0; i < nums.size(); i++) {
			int num1 = nums.get(i), num2 = value - num1;

			if ((num1 == num2 && map.get(num1) > 1) || (num1 != num2 && map.containsKey(num2))) {
				return true;
			}
		}
		return false;
	}

	public static void main(String[] args) {
		// Your TwoSum object will be instantiated and called as such:
		TwoSumDesign twoSum = new TwoSumDesign();

		twoSum.testcase1();
		twoSum.testcase2();
		twoSum.testcase3();

	}

	public void testcase1() {
		TwoSumDesign twoSum = new TwoSumDesign();
		for (int number : new int[] { 1, 3, 5, 8 }) {
			twoSum.add(number);
		}

		int value = 4;
		System.out.println(" find(" + value + ") = " + twoSum.find(value));

		value = 7;
		System.out.println(" find(" + value + ") = " + twoSum.find(value));
	}

	public void testcase2() {
		TwoSumDesign twoSum = new TwoSumDesign();
		int number = 0;
		twoSum.add(number);

		int value = 0;
		System.out.println(" find(" + value + ") = " + twoSum.find(value));
	}

	// [add(3),add(2),add(1),find(2),find(3),find(4),find(5),find(6)]

	public void testcase3() {
		TwoSumDesign twoSum = new TwoSumDesign();

		twoSum.add(3);
		twoSum.add(2);
		twoSum.add(1);

		int value = 2;
		System.out.println(" find(" + value + ") = " + twoSum.find(value)); // false

		value = 3;
		System.out.println(" find(" + value + ") = " + twoSum.find(value)); // true

		value = 4;
		System.out.println(" find(" + value + ") = " + twoSum.find(value)); // true

		value = 5;
		System.out.println(" find(" + value + ") = " + twoSum.find(value)); // true

		value = 6;
		System.out.println(" find(" + value + ") = " + twoSum.find(value)); // false
	}

}