力扣链接：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]
约束:
2 <= nums.length <= 10^4-10^9 <= nums[i] <= 10^9-10^9 <= target <= 10^9- 只会存在一个有效答案
提示 1
A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.
提示 2
So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?
提示 3
The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?
思路
暴力解法的时间复杂度为
O(n**2)，想提升效率，可以对数组进行排序，然后用双指针，一个指向数组头，一个指向数组尾，根据和情况决定left += 1还是right -= 1。对数值数组排序后，想知道某个数值对应的原来的索引下标，有两种方案：
- 方案1：在排序时带上索引下标，即排序的对象是元组点击查看答案
(num, index)的数组。这个技术一定要掌握，许多题目都会用到。
- 方案2：使用index() 查找，已经放到另外一个题解中讲解。
复杂度
时间复杂度
O(N * log N)
空间复杂度
O(N)
Python #
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_index_list = [(num, i) for i, num in enumerate(nums)]
num_index_list.sort()
left = 0
right = len(nums) - 1
while left < right:
sum_ = num_index_list[left][0] + num_index_list[right][0]
if sum_ == target:
return [num_index_list[left][1], num_index_list[right][1]]
if sum_ < target:
left += 1
continue
right -= 1
其它语言
欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 1. 两数之和。题解2的思路：使用 Map
Map中，key是num，value是数组index。- 遍历数组，如果
target - num在Map中，返回。反之，将num加入Map中。
步骤
Map中，key是num，value是数组index。let numToIndex = new Map() for (let i = 0; i < nums.length; i++) { numToIndex.set(nums[i], i) }遍历数组，如果
target - num在Map中，返回。反之，将num加入Map中。let numToIndex = new Map() for (let i = 0; i < nums.length; i++) { if (numToIndex.has(target - nums[i])) { // 1 return [numToIndex.get(target - nums[i]), i] // 2 } numToIndex.set(nums[i], i) }
复杂度
时间复杂度
O(N)
空间复杂度
O(N)
Java #
class Solution {
public int[] twoSum(int[] nums, int target) {
var numToIndex = new HashMap<Integer, Integer>();
for (var i = 0; i < nums.length; i++) {
if (numToIndex.containsKey(target - nums[i])) {
return new int[]{numToIndex.get(target - nums[i]), i};
}
numToIndex.put(nums[i], i);
}
return null;
}
}
Python #
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
num_to_index = {}
for i, num in enumerate(nums):
if target - num in num_to_index:
return [num_to_index[target - num], i]
num_to_index[num] = i
C++ #
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> num_to_index;
for (auto i = 0; i < nums.size(); i++) {
if (num_to_index.contains(target - nums[i])) {
return {num_to_index[target - nums[i]], i};
}
num_to_index[nums[i]] = i;
}
return {};
}
};
JavaScript #
var twoSum = function (nums, target) {
let numToIndex = new Map()
for (let i = 0; i < nums.length; i++) {
if (numToIndex.has(target - nums[i])) {
return [numToIndex.get(target - nums[i]), i]
}
numToIndex.set(nums[i], i)
}
};
C# #
public class Solution {
public int[] TwoSum(int[] nums, int target) {
var numToIndex = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++) {
if (numToIndex.ContainsKey(target - nums[i])) {
return [numToIndex[target - nums[i]], i];
}
numToIndex[nums[i]] = i;
}
return null;
}
}
Go #
func twoSum(nums []int, target int) []int {
numToIndex := map[int]int{}
for i, num := range nums {
if index, ok := numToIndex[target - num]; ok {
return []int{index, i}
}
numToIndex[num] = i
}
return nil
}
Ruby #
def two_sum(nums, target)
num_to_index = {}
nums.each_with_index do |num, i|
if num_to_index.key?(target - num)
return [num_to_index[target - num], i]
end
num_to_index[num] = i
end
end
其它语言
欢迎贡献代码到我们的 GitHub 仓库，非常感谢！本题解位置在 1. 两数之和。题解3的思路：双指针2
- 暴力解法的时间复杂度为
O(n^2)，想提升效率，可以对数组进行排序，然后用双指针，一个指向数组头，一个指向数组尾，根据和情况决定left += 1还是right -= 1。 - 找出了两个值后，需要用
index()方法去找值对应的index。
复杂度
时间复杂度
O(N * log N)
空间复杂度
O(N)
Python #
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
original_nums = nums.copy()
nums.sort()
left = 0
right = len(nums) - 1
while left < right:
sum_ = nums[left] + nums[right]
if sum_ == target:
break
if sum_ < target:
left += 1
continue
right -= 1
return [
original_nums.index(nums[left]),
len(nums) - 1 - original_nums[::-1].index(nums[right])
]