題目
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
题目分析
我们要在数组中找到两个数之和等于目标值，暴力的做法是遍历穷举两个数字。为了避免数量级达到$10^5$的时候超时，我需要用空间换时间，采用hash map存储已经访问过的元素的下标，进行二次匹配，这样的时间复杂度就降低到$O(n)$。
解法
1、暴力枚举
两层循环，枚举找到符合要求的数字。
// java
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(target == nums[i]+nums[j]) {
return new int[] {i,j};
}
}
}
}
# python
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
for i in range(len(nums)):
for j in range(i+1,len(nums)):
# 双层循环进行求和判断
if target == nums[i]+nums[j]:
return [i,j]
func twoSum(nums []int, target int) []int {
// go for loop
for i := 0; i < len(nums); i++ {
for j := i+1; j < len(nums); j++ {
if target == nums[i]+nums[j] {
return []int{i,j}
}
}
}
return []int{}
}
2、用Map存储已经遍历过的元素的下标，进行搜索
遍历每个元素，哈希表中查找已经有的数字，如果没有加入哈希表。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<Integer,Integer>();
for (int i = 0; i < nums.length; i++) {
int newtarget = target - nums[i];
if(map.containsKey(newtarget)) {
return new int[] {map.get(newtarget),i};
}
map.put(nums[i],i);// 之前没有匹配的数字，放入到Map中
}
}
# python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map = {}
for i in range(len(nums)):
newtarget = target - nums[i]
if newtarget in map:
return [map[newtarget],i]
map[nums[i]] = i
func twoSum(nums []int, target int) []int {
// init a map
mapTarget := make(map[int]int)
for i := 0; i < len(nums); i++ {
// if find then return
// use go map use case
value,ok := mapTarget[nums[i]]
if ok {
return []int{value,i}
}
mapTarget[target-nums[i]] = i
}
return []int{}
}
// swift
class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var map = [Int:Int]()
// swift for loop
for i in 0..<nums.count {
let newtarget = target - nums[i]
if let existingIndex = map[newtarget] { // 解包可选值
return [existingIndex, i] // 直接使用解包后的Int值
}
map[nums[i]] = i
}
return []
}
}
如果找对应的值，可以 排序 + 二分搜索 $O(nlogn)$ $O(1)$
update 2024-05-18
由于是返回数值，所以可以先排序，遍历并二分搜索目标值。事件复杂度$O(nlogn)$
// java
class Solution {
public int[] twoSum(int[] nums, int target) {
Arrays.sort(nums); // 排序
for (int i = 0; i < nums.length; i++) {
int l = i + 1, r = nums.length - 1;
int left = target - nums`[i];
// 二分搜索
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == left) {
return new int[] { nums[i], left };
} else if (nums[mid] < left) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return new int[] { -1, -1 };
}
}
# python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
nums.sort()
for i in range(len(nums)):
l = i + 1
r = len(nums) - 1
left = target - nums[i]
while l <= r:
mid = (l + r) // 2
if nums[mid] == left:
return [nums[i], left]
# 找到就返回
# 否则继续二分搜索
elif nums[mid] < left:
l = mid + 1
else:
r = mid - 1
return [-1, -1]
# 如果没有找到就返回-1
转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 1056615746@qq.com
