LeetCode 75 Level 1 - Day 13 Hashmap

1. Two Sum

• 題目連結
• 難易度：Easy

題目敘述

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
You can return the answer in any order.

預設函數

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize){

}

題目限制

• 2 <= nums.length <=
• <= nums[i] <=
• <= target <=
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than time complexity?

解題過程及程式碼

本題給一個整數陣列nums[i]和一個目標值target，要輸出一對位置[i, j]表示nums[i] + nums[j] = target，注意解答只有一個。

首先使用雙迴圈計算所有可能(i, j)情況，因為解答只有一個，所以找到後就可以結束迴圈了

• 程式碼：

int output[2] = {0};

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    int break_flag = 0;
    
    *returnSize = 2;
    
    for (int i=0; i<numsSize; i++) {
        for (int j=i+1; j<numsSize; j++) {
            if ((nums[i] + nums[j]) == target) {
                output[0] = i;
                output[1] = j;
                break_flag = 1;
                break;
            }
        }
        if (break_flag) {
            break;
        }
    }
    return output;
}

題目延伸

題目附加說明到是否時間複雜度可以小於 ?
想法使用Hashmap存放 (target - nums[i]) 的值，邊遍歷邊建表，只要for迴圈走過一次就檢查完畢：

• i=0時，nums[0]時先建表，放入陣列位置是在 hash index = abs(nums[0] % HASH_SIZE)，內容有2個元素： index{i=0} 和 val{target - nums[0]}。
• i>0時，nums[i] -> 檢查陣列位置 abs((target - nums[i]) % HASH_SIZE) 中的val是否和nums[i]相同：
  • 若"是"則找到兩個數和為 target。
  • 若"否"則將 nums[i] 繼續建表。

hash程式碼上傳：

#define HASH_SIZE 200

typedef struct {
    int index;
    int val;
} element;

int output[2] = {0};

int* twoSum(int* nums, int numsSize, int target, int* returnSize){
    element hash[HASH_SIZE] = {NULL};
    element node;

    node.index = 0;
    node.val = target - nums[0];
    hash[hash_function(nums[0])] = node;

    for (int i=1; i<numsSize; i++) {
        if (hash[hash_function(target - nums[i])].val == nums[i]) {
            output[0] = hash[hash_function(target - nums[i])].index;
            output[1] = i;
            break;
        } else {
            node.index = i;
            node.val = target - nums[i];
            hash[hash_function(nums[i])] = node;
        }
    }
    *returnSize = 2;
    return output;
}

int hash_function(int key) {
    return abs(key % HASH_SIZE);
}

謝謝看到這邊。