給定一個整數數組 nums 和一個整數目標值 target，請你在該數組中找出 和為目標值 target 的那 兩個 整數，并返回它們的數組下標。

你可以假設每種輸入只會對應一個答案，并且你不能使用兩次相同的元素。

你可以按任意順序返回答案。

示例 1：

輸入：nums = [2,7,11,15], target = 9
輸出：[0,1]
解釋：因為 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：

輸入：nums = [3,2,4], target = 6
輸出：[1,2]
示例 3：

輸入：nums = [3,3], target = 6
輸出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只會存在一個有效答案

1.自解

方法一，雙重for循環

時間、空間復雜度都比較差
最純粹的暴力遍歷，使用了兩個for循環

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int*p=(int *)malloc(sizeof(int)*2);
    int num1=0,num2=0;
    for(int i=0;i<numsSize;i++)
    {
        for(int j=i+1;j<numsSize;j++)
        {
            if(nums[i]+nums[j]==target)
            {
                p[0]=i;
                p[1]=j;
                *returnSize=2;
                return p;
            }
        }
    }
    *returnSize=0;
    return NULL;

}

方法二：哈希表

參考了官方解答，但是自己寫的
簡單的來說就是遍歷一次數組，將沒能成功組成目標數的數用一個鏈表儲存起來，遇到新的數直接和鏈表里的數進行匹配，匹配到就直接輸出，未匹配到就加入鏈表。
第一次寫的時候只使用了頭節點，因此插入鏈表尾部也要遍歷一次鏈表，花費時間較多

第二次的時候用了一個尾節點，新元素直接插入鏈表尾部，節省了許多時間

與官方解答對比可以發現差不多，不過官方使用了HASH_ADD_INT與HASH_FIND_INT兩個庫函數，但是時間直接快到3ms，只能說庫函數偉大，無需多言，要拒絕重復造輪子

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
struct hashtable{//鏈表的節點
    int key;
    int val;
    struct hashtable*next;
};
struct hashtable *head=NULL;//頭部
struct hashtable *tail=NULL;//尾部
struct hashtable* hashtable_find(int val)//遍歷鏈表內查找
{
    struct hashtable *temp=head;
    while(temp!=NULL&&temp->val!=val)temp=temp->next;
    return temp;
}
void hashtable_insert(struct hashtable* insert_ht)//新節點插入尾部
{
    if(head==NULL)
	{
		head=insert_ht;
		tail=insert_ht;
		return ;
	}
    struct hashtable *temp=head;
    tail->next=insert_ht;
    tail=insert_ht;
}
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    int *r=(int *)malloc(sizeof(int)*2);
    struct hashtable* temp;
    head=NULL;
    for(int i=0;i<numsSize;i++)
    {
        if((temp=hashtable_find(target-nums[i]))!=NULL)//鏈表中查到與匹配節點
        {

            r[0]=i;
            r[1]=temp->key;
            *returnSize=2;
            return r;
        }
        else
        {//無匹配節點，當前數插入鏈表
            temp=(struct hashtable *)malloc(sizeof(struct hashtable));
            temp->key=i;
            temp->val=nums[i];
            temp->next=NULL;
            hashtable_insert(temp);
        }
    }
    return r;
}

官方解

哈希表，用到了庫函數

struct hashTable {
    int key;
    int val;
    UT_hash_handle hh;
};

struct hashTable* hashtable;

struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);
    return tmp;
}

void insert(int ikey, int ival) {
    struct hashTable* it = find(ikey);
    if (it == NULL) {
        struct hashTable* tmp = malloc(sizeof(struct hashTable));
        tmp->key = ikey, tmp->val = ival;
        HASH_ADD_INT(hashtable, key, tmp);
    } else {
        it->val = ival;
    }
}

int* twoSum(int* nums, int numsSize, int target, int* returnSize) {
    hashtable = NULL;
    for (int i = 0; i < numsSize; i++) {
        struct hashTable* it = find(target - nums[i]);
        if (it != NULL) {
            int* ret = malloc(sizeof(int) * 2);
            ret[0] = it->val, ret[1] = i;
            *returnSize = 2;
            return ret;
        }
        insert(nums[i], i);
    }
    *returnSize = 0;
    return NULL;
}

作者：力扣官方題解
鏈接：https://leetcode.cn/problems/two-sum/solutions/434597/liang-shu-zhi-he-by-leetcode-solution/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯系作者獲得授權，非商業轉載請注明出處。