Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.
Example:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].Input: nums = [3,2,4], target = 6
Output: [1,2]Input: nums = [3,3], target = 6
Output: [0,1]问题
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。
解决方案 1
使用哈希表来记录每个数值对应的索引，以便快速查找是否存在目标值减去当前值的数。
Approach 1 / 方法 1
遍历数组，对于每个元素，检查哈希表中是否存在与当前元素之和为目标值的元素。如果存在，返回两个元素的索引。如果不存在，将当前元素添加到哈希表中。
Detailed Steps / 详细步骤
Initialization / 初始化:
- Initialize an empty hash table (dictionary).
初始化一个空的哈希表（字典）。
Step 1 / 第一步:
- Iterate through the array, and for each element, calculate the complement (target – current element).
遍历数组，对于每个元素，计算补数（目标值减去当前元素）。
Step 2 / 第二步:
- Check if the complement exists in the hash table. If it does, return the indices of the current element and the complement.
检查哈希表中是否存在补数。如果存在，返回当前元素和补数的索引。
Step 3 / 第三步:
- If the complement does not exist, add the current element and its index to the hash table.
如果补数不存在，将当前元素及其索引添加到哈希表中。
Implementation / 实现
python
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
num_map = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_map:
return [num_map[complement], i]
num_map[num] = iExplanation / 解释
- Step 1 / 第一步:
- Initialize an empty hash table
num_map.
初始化一个空的哈希表num_map。
- Step 2 / 第二步:
- For each element, calculate the complement and check if it exists in
num_map.
对于每个元素，计算补数并检查它是否存在于num_map中。
- Step 3 / 第三步:
- If the complement exists, return the indices; otherwise, add the current element to
num_map.
如果补数存在，返回索引；否则，将当前元素添加到num_map中。
Complexity Analysis / 复杂度分析
-
Time Complexity: O(N), where N is the number of elements in the array.
时间复杂度: O(N)，其中 N 是数组中的元素数量。 -
Space Complexity: O(N), to store the elements in the hash table.
空间复杂度: O(N)，用于存储哈希表中的元素。
Key Concept / 关键概念
- The key concept is to use a hash table to achieve constant time lookups for the complement of each element.
关键概念是使用哈希表实现每个元素补数的常量时间查找。
解决方案 2
使用双指针方法在排序后的数组中查找两个数。
Approach 2 / 方法 2
先对数组进行排序，然后使用双指针从数组的两端开始查找和为目标值的两个数。
Detailed Steps / 详细步骤
Initialization / 初始化:
- Sort the array and initialize two pointers, one at the beginning and one at the end.
对数组进行排序，并初始化两个指针，一个指向数组的开头，一个指向数组的末尾。
Step 1 / 第一步:
- Calculate the sum of the elements at the two pointers.
计算两个指针指向元素的和。
Step 2 / 第二步:
- If the sum is equal to the target, return the indices.
如果和等于目标值，返回索引。
Step 3 / 第三步:
- If the sum is less than the target, move the left pointer to the right.
如果和小于目标值，左指针向右移动。
Step 4 / 第四步:
- If the sum is greater than the target, move the right pointer to the left.
如果和大于目标值，右指针向左移动。
Implementation / 实现
python
class Solution:
def twoSum(self, nums: list[int], target: int) -> list[int]:
nums_with_index = list(enumerate(nums))
nums_with_index.sort(key=lambda x: x[1])
left, right = 0, len(nums) - 1
while left < right:
sum = nums_with_index[left][1] + nums_with_index[right][1]
if sum == target:
return [nums_with_index[left][0], nums_with_index[right][0]]
elif sum < target:
left += 1
else:
right -= 1Explanation / 解释
- Step 1 / 第一步:
- Sort the array while keeping track of the original indices.
对数组进行排序，同时跟踪原始索引。
- Step 2 / 第二步:
- Initialize two pointers and calculate the sum of the elements they point to.
初始化两个指针，并计算它们指向的元素的和。
- Step 3 / 第三步:
- Adjust the pointers based on whether the sum is less than or greater than the target.
根据和是小于还是大于目标值调整指针。
Complexity Analysis / 复杂度分析
-
Time Complexity: O(N log N), for sorting the array.
时间复杂度: O(N log N)，用于排序数组。 -
Space Complexity: O(N), for storing the sorted elements and their indices.
空间复杂度: O(N)，用于存储排序后的元素及其索引。
Key Concept / 关键概念
- The key concept is to use the two-pointer technique on a sorted array to find two numbers that add up to the target.
关键概念是在排序数组上使用双指针技术找到和为目标值的两个数。
Tips / 提示
- Remember that the problem guarantees exactly one solution.
记住问题保证恰好有一个解。
Solution Template for similar questions / 提示
- The general approach can be applied to other problems involving finding pairs in an array that meet a certain condition.
通用方法可以应用于其他涉及在数组中寻找满足特定条件的对的问题。
Recommended 5 more similar questions / 推荐5问题
- LeetCode 167: Two Sum II – Input array is sorted
- LeetCode 653: Two Sum IV – Input is a BST
- LeetCode 15: 3Sum
- LeetCode 18: 4Sum
- LeetCode 560: Subarray Sum Equals K
More
- LeetCode Explore – Array
- GeeksforGeeks – Hashing in Data Structures
- InterviewBit – Hashing Interview Questions
- Neetcode 150
This should give a clear, comprehensive guide on solving the problem with detailed steps, explanations, and additional resources for practice.
Leave a Reply