摘要：1. 两数之和 题目描述给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。 示例:...

1. 两数之和

题目描述

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

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

解题思路

1. 暴力法：双重循环遍历数组，找到两个数之和等于目标值，返回它们的下标。时间复杂度为O(n^2)，空间复杂度为O(1)。

2. 哈希表法：遍历数组，将每个元素的值和它的下标存入哈希表中。在遍历的同时，检查哈希表中是否存在目标值减去当前元素的值，如果存在，则返回它们的下标。时间复杂度为O(n)，空间复杂度为O(n)。

代码实现

暴力法

java

class Solution {

public int[] twoSum(int[] nums, int target) {

for (int i = 0; i < nums.length; i++) {

for (int j = i + 1; j < nums.length; j++) {

if (nums[i] + nums[j] == target) {

return new int[] {i, j};

}

}

}

throw new IllegalArgumentException("No two sum solution");

}

}

哈希表法

java

class Solution {

public int[] twoSum(int[] nums, int target) {

Map 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");

}

}

复杂度分析

暴力法

时间复杂度：O(n^2)，其中n是数组的长度。最坏情况下，需要遍历数组中的每个元素两次。

空间复杂度：O(1)，只使用了常数个额外空间。

哈希表法

时间复杂度：O(n)，其中n是数组的长度。只需要遍历一次数组，每次查找哈希表的时间复杂度为O(1)。

空间复杂度：O(n)，其中n是数组的长度。最坏情况下，需要将数组中的所有元素存入哈希表中。