本文主要是介绍第一题：两数之和，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
LeetCode 第一道题目 “两数之和”（Two Sum）的详细解题思路和三种语言的实现如下：
题目描述
给定一个整数数组 nums 和一个整数 target，请你在数组中找出和为 target 的两个数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
你可以按任意顺序返回答案。
解题思路
我们可以使用以下方法来解决这个问题：
-
暴力法：使用两个嵌套的循环遍历所有可能的两数组合，检查是否有两个数的和等于
target。时间复杂度是 O(n^2)，空间复杂度是 O(1)。 -
哈希表法：利用哈希表存储每个元素及其下标。在遍历数组时，计算
target - nums[i]，然后检查这个值是否已经在哈希表中。如果在哈希表中找到了，则找到了满足条件的两个数，可以立即返回它们的下标。时间复杂度是 O(n)，空间复杂度是 O(n)，因为哈希表的插入和查找操作的平均时间复杂度是 O(1)。
C 语言实现
#include <stdio.h>
#include <stdlib.h>#define HASH_SIZE 10000// 哈希表节点
typedef struct {int key;int value;
} HashNode;// 哈希表
typedef struct {HashNode* table[HASH_SIZE];
} HashMap;// 初始化哈希表
void initHashMap(HashMap* map) {for (int i = 0; i < HASH_SIZE; i++) {map->table[i] = NULL;}
}// 哈希函数
int hash(int key) {return abs(key) % HASH_SIZE;
}// 插入哈希表
void insert(HashMap* map, int key, int value) {int index = hash(key);HashNode* node = (HashNode*)malloc(sizeof(HashNode));node->key = key;node->value = value;map->table[index] = node;
}// 查找哈希表
int search(HashMap* map, int key) {int index = hash(key);return map->table[index] ? map->table[index]->value : -1;
}// 两数之和
int* twoSum(int* nums, int numsSize, int target, int* returnSize) {HashMap map;initHashMap(&map);int* result = (int*)malloc(2 * sizeof(int));*returnSize = 2;for (int i = 0; i < numsSize; i++) {int complement = target - nums[i];int index = search(&map, complement);if (index != -1) {result[0] = index;result[1] = i;return result;}insert(&map, nums[i], i);}return NULL;
}int main() {int nums[] = {2, 7, 11, 15};int target = 9;int returnSize;int* result = twoSum(nums, 4, target, &returnSize);if (result) {printf("Indices: %d, %d\n", result[0], result[1]);free(result);}return 0;
}
Java 实现
import java.util.HashMap;
import java.util.Map;public class TwoSum {public static int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int complement = target - nums[i];if (map.containsKey(complement)) {return new int[] { map.get(complement), i };}map.put(nums[i], i);}throw new IllegalArgumentException("No two sum solution");}public static void main(String[] args) {int[] nums = {2, 7, 11, 15};int target = 9;int[] result = twoSum(nums, target);System.out.println("Indices: " + result[0] + ", " + result[1]);}
}
Python 实现
def two_sum(nums, target):num_to_index = {}for i, num in enumerate(nums):complement = target - numif complement in num_to_index:return [num_to_index[complement], i]num_to_index[num] = iraise ValueError("No two sum solution")# 示例使用
nums = [2, 7, 11, 15]
target = 9
result = two_sum(nums, target)
print(f"Indices: {result[0]}, {result[1]}")
时间复杂度
-
暴力法：
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
-
哈希表法：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
总结
- 暴力法：时间复杂度较高，但实现简单。适合数据量小的情况。
- 哈希表法：时间复杂度较低，适合数据量大的情况，使用哈希表可以显著提高效率。
这篇关于第一题：两数之和的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
