Problem
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
1
2
3
4
5
6Example:
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
给定一个数组,一个数字target, 在数组中查找两个数之和等于target. 返回查找的下标.
假定每个target只有一个solution,不能重复使用元素.
Solution
Analysis
最朴素的办法: 双层循环. 时间复杂度O(N*N). 这个就不介绍了.
改进方法: O(N). 借助hash表[空间换时间]. hash表记录元素与下标对应关系. 这里我们不用事先对hash表进行初始化. 边循环数组边赋值: 如果查找元素不存在,进行赋值.
具体代码如下:
Code
1 | class Solution { |