Two Sum III - Data structure design

Two Sum III - Data structure design

Account Login - LeetCode

- 문제 내용 : Two Sum API 개발

- 접근 방법

일반적인 Two Sum과 같기 때문에 큰 문제는 없는데 Edge Case가 2가지가 있어서 해당 부분을 남기고자 한다.

• Array에 한개의 값만 있는데 정답이 되는 경우
  • 예를 들자면 0의 경우는 0을 찾게 되는데 이때 0이 Array에 하나밖에 없다면 false
• 동일 값이 2번 연속되는 경우
  • 예를 들자면 찾는 값이 4이고 2를 찾을 경우 2가 있다해도 2개 이상이 필요 한 경우 하나만 있으면 false

이와 같은 edge case만 해결 한다면 문제 해결에 문제는 없다.

이를 해결하기 위해서 Hash map에 add된 Integer의 횟수를 기록해 놓고 이를 사용한다.

//TwoSum() Initializes the TwoSum object, with an empty array initially
var TwoSum = function() {
    this.array = new Array();
    this.map = new Map();
};

//void add(int number) Adds number to the data structure.
TwoSum.prototype.add = function(number) {
    this.array.push(number);
    this.map.set(number, ~~this.map.get(number) + 1);
};

//boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.
TwoSum.prototype.find = function(value) {
    for (let i = 0; i < this.array.length; i++) {
        let findValue = value - this.array[i];
        if(this.map.has(findValue)){
            if(findValue === value || findValue * 2 === value){
                if(1 < this.map.get(findValue)){
                    return true;
                }
            } else {
                return true;
            }
        }
    }
    return false;
};