Leetcode - 1. Two Sum 풀이

문제

배열값과 target 값이 주어질때, 배열의 서로다른 두 index의 값을 더해서 target값이 나오는 index쌍을 구하라.

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

해결 O(N^2)

brute force

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int *)malloc(sizeof(int) * 2);
    memset(ret, 0, sizeof(int) * 2);
    *returnSize = 2;
    
    for (int i = 0; i < numsSize; i++) {
        ret[0] = i;
        for (int j = 0; j < numsSize; j++) {
            if ((nums[i] + nums[j] == target) && i != j) {
                ret[1] = j;
                return ret;
            }
        }
    }
    return ret;  
}

해결 O(N)

배열값을 먼저 해시테이블에 저장하고, 배열을 다시 순회하면서 target이 되기 위한 나머지값이 해시테이블에 존재하는지 파악.

1. Constraints
 - -10^9 <= nums[i], target <= 10^9
 - 2 <= nums.length <= 10^4
 - nums[i] can be duplicated.

 
2. Ideas
 - brute force -> O(N^2)
 - sort then, linear search or binary search -> O(NlogN)
 - hashtable -> O(N)
 
3. Test Cases
 - [0, 1] 1
 - [1, 2, 2, 4] 5
 - [1, 2, 2, 4] 3 <- there would not be

이것은 처음 구현했을때, O(N) + O(N) 을 두번 해서 비효율적.
그리고 해시테이블에서 꺼낸 값이 자기 자신의 idx가 아닌것을 체크해야해서 코드상 더 복잡함.

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int *)calloc(2, sizeof(int));
    if (!ret) fprintf(stderr, "no memory");
    memset(table, 0, sizeof(struct elem *) * HSIZE);
    int search = 0;
    struct elem *found;
    *returnSize = 2;
    
    for (int i = 0; i < numsSize; i++)
        hash_add(nums[i], i);

    for (int i = 0; i < numsSize; i++) {
        search = target - nums[i];
        found = hash_search(search);
        if (found && i != found->idx) {
            ret[0] = i;
            ret[1] = found->idx;
            break;
        }
    }
    hash_free();
    return ret;
}

다음은 더 효율적 솔루션 O(N)한번만 한다. 코드도 더 간결.

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int *)calloc(2, sizeof(int));
    if (!ret) fprintf(stderr, "no memory");
    memset(table, 0, sizeof(struct elem *) * HSIZE);
    int search = 0;
    struct elem *found;
    *returnSize = 2;
    
    for (int i = 0; i < numsSize; i++) {
        search = target - nums[i];
        found = hash_search(search);
        if (found) {
            ret[0] = i;
            ret[1] = found->idx;
            break;
        } else {
            hash_add(nums[i], i);
        }
    }
    //hash_free();
    return ret;
}

다음은 구현했던 해시테이블 자료구조.

#define HSIZE 10093
struct elem {
    int val;
    int idx;
    struct elem *next;
};
struct elem *table[HSIZE];

int hash(int val)
{
    val = val < 0 ? -val : val;
    return val % HSIZE;
}

void hash_add(int val, int idx)
{
    int hval = hash(val);
    struct elem *node = (struct elem *)malloc(sizeof(struct elem));
    
    node->val = val;
    node->idx = idx;
    node->next = table[hval];
    table[hval] = node;
}

struct elem *hash_search(int val)
{
    int hval = hash(val);
    struct elem *node = table[hval];
    
    for (;node != NULL; node = node->next) {
        if (node->val == val)
            return node;
    }
    return node;
}

void hash_free(void)
{
    for (int i = 0; i < HSIZE; i++)
        if (table[i])
            free(table[i]);
}

230121 다시 풀어봄

c++ stl unordered_map 사용.
해시 테이블을 순회 할때, for문을 두번 사용할 필요없이, 한번만 순회하면서 key를 못찾으면 삽입하고 찾으면 필요한동작을 수행하는게 효율적이다. 이 구조를 잘 기억할것!

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret(2, 0);
        unordered_map<int, int> map; // nums[index], index
        
        for (int i = 0; i < nums.size(); i++) {
            if (map.find(target - nums[i]) != map.end()) {
                if (map[target - nums[i]] == i)
                    continue;
                ret[0] = map[target - nums[i]];
                ret[1] = i;
                break;
            } else {
                map[nums[i]] = i;
            }
        }
        return ret;
    }
};
``