题目来源
题目描述
给定一个整数数组 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 <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- 只会存在一个有效答案
题目解析
本题我们只需要遍历一遍数组 nums 即可找出数组中 "和为 target" 的两个元素及其索引位置。
具体实现是：
- 首先，定义一个字典dic（哈希表），用于记录已遍历过的数组元素和其索引位置，即字典的key为数组元素，value为数组元素的索引位置。
- 然后，遍历数组 nums，假设此时被遍历出来的元素是 num，索引位置为 index，那么满足要求的另一个元素应该是 target - num，因此我们可以在字典 dic 中查找是否存在 target - num：
- 若存在，则找到了符合要求的两个数组元素，他们的位置分别是：index 和 dic[target - num]
- 若不存在，则我们应该记录此时 num 的索引位置 index，即 dic[num] = index
按照上面逻辑，遍历完所有数组元素，即可找到题解。
C源码实现
C语言没有内置的哈希表实现，因此下面我们自己手搓了一个简易的哈希表。
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
typedef struct Node {
int num;
int index;
struct Node *next;
} Node;
typedef struct Link {
Node *head;
} Link;
typedef struct HashTable {
Link **buckets;
int buckets_size;
} HT;
Node *new_Node(int num, int index) {
Node *node = (Node *) malloc(sizeof(Node));
node->num = num;
node->index = index;
node->next = NULL;
return node;
}
Link *new_Link() {
Link *link = (Link *) malloc(sizeof(Link));
link->head = NULL;
return link;
}
HT *new_HashTable(int buckets_size) {
HT *ht = (HT *) malloc(sizeof(HT));
ht->buckets_size = buckets_size;
ht->buckets = (Link **) calloc(buckets_size, sizeof(Link *));
return ht;
}
int get_HashTable(HT *ht, int num) {
int buckets_index = abs(num % ht->buckets_size);
Link *link = ht->buckets[buckets_index];
if (link != NULL) {
Node *cur = link->head;
while (cur != NULL) {
if (cur->num == num) {
return cur->index;
}
cur = cur->next;
}
}
return -1;
}
void put_HashTable(HT *ht, int num, int index) {
int buckets_index = abs(num % ht->buckets_size);
if (ht->buckets[buckets_index] == NULL) {
ht->buckets[buckets_index] = new_Link();
}
Node *cur = ht->buckets[buckets_index]->head;
while (cur != NULL) {
if (cur->num == num) {
cur->index = index;
return;
}
cur = cur->next;
}
Node *node = new_Node(num, index);
if (ht->buckets[buckets_index]->head != NULL) {
node->next = ht->buckets[buckets_index]->head;
}
ht->buckets[buckets_index]->head = node;
}
int *twoSum(int *nums, int numsSize, int target, int *returnSize) {
int *result = (int *) malloc(sizeof(int) * 2);
*returnSize = 2; // 记录返回值result数组有几个元素
// 哈希表用于记录已遍历过的数组元素及其索引位置，key为数组元素，value为数组元素的索引位置
HT *ht = new_HashTable(100000); // 初始化哈希表的容量
for (int i = 0; i < numsSize; i++) { // 遍历数组元素
int remain = target - nums[i];
int index = get_HashTable(ht, remain); // 检查已遍历过的数组元素中是否有 target - nums[i]
if (index != -1) { // 若有， 则找到了和为target的两个数组元素的索引位置
result[0] = index;
result[1] = i;
return result;
} else { // 若没有，则记录 nums[i] 和其索引位置 i
put_HashTable(ht, nums[i], i);
}
}
return result;
}
C++源码实现
unordered_map性能要比map好一点，find操作要比count操作性能更好一点
class Solution {
public:
vector<int> twoSum(vector<int> &nums, int target) {
unordered_map<int, int> dic; // 记录已遍历过的数组元素及其索引位置，key为数组元素，value为数组元素的索引位置
for (int i = 0; i < nums.size(); i++) {
int remain = target - nums[i];
if (dic.find(remain) != dic.end()) { // 检查已遍历过的数组元素中是否有 target - nums[i]
return vector < int > {dic[remain], i}; // 若有， 则找到了和为target的两个数组元素的索引位置
} else {
dic[nums[i]] = i; // 若没有，则记录 nums[i] 和其索引位置 i
}
}
return {};
}
};
Java源码实现
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<>(); // 记录已遍历过的数组元素及其索引位置，key为数组元素，value为数组元素的索引位置
for (int i = 0; i < nums.length; i++) {
int remain = target - nums[i];
if (map.containsKey(remain)) { // 检查已遍历过的数组元素中是否有 target - nums[i]
return new int[] { map.get(remain), i }; // 若有， 则找到了和为target的两个数组元素的索引位置
} else {
map.put(nums[i], i); // 若没有，则记录 nums[i] 和其索引位置 i
}
}
return null;
}
}
Python源码实现
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
dic = {} # 记录已遍历过的数组元素及其索引位置，key为数组元素，value为数组元素的索引位置
for i in range(len(nums)):
remain = target - nums[i]
if remain in dic: # 检查已遍历过的数组元素中是否有 target - nums[i]
return [dic[remain], i] # 若有，则找到了和为target的两个数组元素的索引位置
else:
dic[nums[i]] = i # 若没有，则记录 nums[i] 和其索引位置 i
return []
JavaScript源码实现
虽然使用JS对象模拟哈希表性能更优一点，但是使用Map类语义化更好一点
/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function(nums, target) {
const map = new Map(); // 记录已遍历过的数组元素及其索引位置，key为数组元素，value为数组元素的索引位置
for(let i=0; i<nums.length; i++) {
const remain = target - nums[i];
if(map.has(remain)) { // 检查已遍历过的数组元素中是否有 target - nums[i]
return [map.get(remain), i]; // 若有， 则找到了和为target的两个数组元素的索引位置
} else {
map.set(nums[i], i); // 若没有，则记录 nums[i] 和其索引位置 i
}
}
return [];
};