面试经典算法题69-两数之和

面试经典算法题69-两数之和

公众号：阿Q技术站
LeetCode.1

问题描述

给定一个整数数组 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]

思路

暴力解法：

• 遍历数组中的每个元素，并对每个元素再次遍历剩下的元素，检查它们的和是否等于目标值 target。

• 时间复杂度是 O(n^2)，其中 n 是数组的长度。

哈希表解法：

• 创建一个哈希表，用于存储数组中的每个元素及其对应的下标。
• 遍历数组，对于每个元素，计算出目标值与该元素的差值，并检查这个差值是否存在于哈希表中。
• 如果存在，说明找到了两个数，它们的和等于目标值，返回这两个数的下标。
• 否则，将当前元素及其下标存入哈希表，继续遍历。
• 时间复杂度是 O(n)，其中 n 是数组的长度，因为每个元素最多只需遍历一次。

参考代码

C++

#include <iostream>
#include <vector>
#include <unordered_map>using namespace std;// 在数组中查找和为目标值的两个数的下标
vector<int> twoSum(vector<int>& nums, int target) {// 创建一个哈希表，键为数组中的元素，值为元素的下标unordered_map<int, int> numMap;// 遍历数组for (int i = 0; i < nums.size(); ++i) {// 计算目标值与当前元素的差值int complement = target - nums[i];// 检查差值是否存在于哈希表中if (numMap.find(complement) != numMap.end()) {// 如果存在，返回差值的下标和当前元素的下标return {numMap[complement], i};}// 将当前元素及其下标存入哈希表numMap[nums[i]] = i;}// 如果没有找到符合条件的两个数，返回空数组return {};
}int main() {// 示例输入vector<int> nums1 = {2, 7, 11, 15};int target1 = 9;vector<int> nums2 = {3, 2, 4};int target2 = 6;vector<int> nums3 = {3, 3};int target3 = 6;// 调用函数并输出结果vector<int> result1 = twoSum(nums1, target1);cout << "输入：nums = [2,7,11,15], target = 9" << endl;cout << "输出：[" << result1[0] << "," << result1[1] << "]" << endl;vector<int> result2 = twoSum(nums2, target2);cout << "输入：nums = [3,2,4], target = 6" << endl;cout << "输出：[" << result2[0] << "," << result2[1] << "]" << endl;vector<int> result3 = twoSum(nums3, target3);cout << "输入：nums = [3,3], target = 6" << endl;cout << "输出：[" << result3[0] << "," << result3[1] << "]" << endl;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> numMap = new HashMap<>();// 遍历数组for (int i = 0; i < nums.length; i++) {// 计算目标值与当前元素的差值int complement = target - nums[i];// 检查差值是否存在于哈希表中if (numMap.containsKey(complement)) {// 如果存在，返回差值的下标和当前元素的下标return new int[] { numMap.get(complement), i };}// 将当前元素及其下标存入哈希表numMap.put(nums[i], i);}// 如果没有找到符合条件的两个数，返回空数组return new int[] {};}public static void main(String[] args) {// 示例输入int[] nums1 = { 2, 7, 11, 15 };int target1 = 9;int[] nums2 = { 3, 2, 4 };int target2 = 6;int[] nums3 = { 3, 3 };int target3 = 6;// 调用函数并输出结果int[] result1 = twoSum(nums1, target1);System.out.println("输入：nums = [2,7,11,15], target = 9");System.out.println("输出：[" + result1[0] + "," + result1[1] + "]");int[] result2 = twoSum(nums2, target2);System.out.println("输入：nums = [3,2,4], target = 6");System.out.println("输出：[" + result2[0] + "," + result2[1] + "]");int[] result3 = twoSum(nums3, target3);System.out.println("输入：nums = [3,3], target = 6");System.out.println("输出：[" + result3[0] + "," + result3[1] + "]");}
}

Python

def two_sum(nums, target):# 创建一个字典，键为数组中的元素，值为元素的下标num_map = {}# 遍历数组for i, num in enumerate(nums):# 计算目标值与当前元素的差值complement = target - num# 检查差值是否存在于字典中if complement in num_map:# 如果存在，返回差值的下标和当前元素的下标return [num_map[complement], i]# 将当前元素及其下标存入字典num_map[num] = i# 如果没有找到符合条件的两个数，返回空数组return []# 示例输入
nums1 = [2, 7, 11, 15]
target1 = 9
nums2 = [3, 2, 4]
target2 = 6
nums3 = [3, 3]
target3 = 6# 调用函数并输出结果
print(f"输入：nums = {nums1}, target = {target1}")
print(f"输出：{two_sum(nums1, target1)}")print(f"输入：nums = {nums2}, target = {target2}")
print(f"输出：{two_sum(nums2, target2)}")print(f"输入：nums = {nums3}, target = {target3}")
print(f"输出：{two_sum(nums3, target3)}")