题目来源：LeetCode第一题

1.题目描述

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

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

示例 1：

输入：nums = [2,7,11,15], target = 9

输出：[0,1]

解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

提示：

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

2.解题思路

解法一：暴力法

• 描述：利用两层嵌套的循环分别遍历数组中的每个元素，检查两层元素的和是否等于目标值，一旦找到和为目标值的两个元素，立即返回这两个元素的索引。
• 时间复杂度：对于每一个元素，我们都遍历数组的其他部分来寻找另一个元素使得它们的和等于目标值。所以总的运算是 n+(n−1)+(n−2)+...+1=n(n+1)/2​，这是 O(n2) 的复杂度。
• 空间复杂度：这种方法不需要额外的存储空间。空间复杂度为O(1)。
• 参考代码：

Java版：

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 外层循环
        for (int i = 0; i < nums.length; i++) {
            // 内层循环从i+1开始，因为题目中说到
            // 数组中同一个元素在答案里不能重复出现
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] + nums[j] == target)
                    return new int[] { i, j };
            }
        }
        return new int[0];
    }
}

C++版:

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		for (int i = 0; i < nums.size(); i++) {
			for (int j = i + 1; j < nums.size(); j++) {
				if (nums[i] + nums[j] == target)
					return { i,j };
			}
		}
		return {};
	}
};

C版：

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

解法二：哈希表法

• 描述：我们可以利用哈希表来存储每个元素和它的索引，单次遍历数组的每一个元素x，检查target-x是否存在哈希表中，如果存在并且索引值和当前元素不同，则找到结果直接返回，若不存在，则将当前元素和其索引值添加到哈希表中。
• 时间复杂度：我们只遍历数组一次，并且对每个元素，在哈希表中查找操作是常数时间（平均情况下）。时间复杂度为O(n)。
• 空间复杂度：最坏的情况下，我们可能需要存储数组中的所有元素。空间复杂度为O(n)。
• 参考代码：

Java版：

public int[] twoSum(int[] nums, int target) {
        // 创建一个哈希表来存储元素及其索引
        Map<Integer, Integer> hashtable = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            // 如果 target-元素 已经存在于哈希表中，说明已经找到
            if (hashtable.containsKey(target - nums[i])) {
                return new int[] { hashtable.get(target - nums[i]), i };
            }
            // 否则将元素及其索引添加进哈希表中
            hashtable.put(nums[i], i);
        }
        return new int[0];
    }

C++版:

class Solution {
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		// 使用unordered_map作为哈希表，存储数字及其在数组中的索引
		unordered_map<int, int> hashtable;

		for(int i=0;i<nums.size();i++)
		{
			// 如果 target-元素 已经存在哈希表中，说明已经找到
			//这里hashtable.find如果找到的话就会返回该键对应的迭代器
			//没有找到就会返回一个指向容器最后一个元素之后位置的迭代器也就是hashtable.end()
			if(hashtable.find(target-nums[i])!=hashtable.end())
			{
				return { hashtable[target - nums[i]],i };
			}
			// 否则，将当前数字及其索引添加到哈希表中
			hashtable[nums[i]] = i;
		}
		return {};
	}
};

C版：

#include <stdio.h>
#include <stdlib.h>
#include "uthash.h"  // 需要包含UTHASH的头文件

// 定义哈希表的节点结构
struct hashTable {
    int key;    // 键：数组中的数字
    int val;    // 值：数字在数组中的索引
    UT_hash_handle hh;  // UTHASH所需要的结构
};

struct hashTable* hashtable;

// 在哈希表中查找指定键的项
struct hashTable* find(int ikey) {
    struct hashTable* tmp;
    HASH_FIND_INT(hashtable, &ikey, tmp);  // UTHASH提供的按int类型键查找的宏
    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);  // UTHASH提供的按int类型键添加的宏
    } else {  // 如果键已存在，则更新
        it->val = ival;
    }
}

// 主要的函数，寻找两个数的索引，使它们的和为target
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) {  // 如果找到了 complement
            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;
}