题目描述
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定： nums = [2, 7, 11, 15], target = 9
返回：[0, 1]
解题思路
1. 遍历法
遍历每个元素x，并查找是否存在一个值与 target−x 相等的目标元素 。两次遍历，第二个遍历从后面一位开始遍历。 对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素。
- 时间复杂度：O(n^2^)
- 空间复杂度：O(1)
Java
class Solution {
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 (nums[j] == target - nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("No two sum solution");
}
}
python
def twoSum(nums, target):
lens = len(nums)
j=-1
for i in range(lens):
if (target - nums[i]) in nums:
if (nums.count(target - nums[i]) == 1)&(target - nums[i] == nums[i]):
#如果num2=num1,且nums中只出现了一次，说明找到是num1本身。
continue
else:
j = nums.index(target - nums[i],i+1)
#index(x,i+1)是从num1后的序列后找num2
break
if j>0:
return [i,j]
else:
return []
此处是从头开始遍历，优化是只要从 num[i]之前或之后遍历就可，例如 if (target - nums[i]) in nums[:i]中遍历， 可以减少运行的时间，虽然时间复杂度都是一样。
def twoSum(nums, target):
lens = len(nums)
j=-1
for i in range(1,lens):
temp = nums[:i]
if (target - nums[i]) in temp:
j = temp.index(target - nums[i])
break
if j>=0:
return [j,i]
2. HashMap 减少查询时间
设置一个 HashMap 容器 record 用来记录元素的值与索引，然后遍历数组 nums。 使用一层循环，每遍历到一个元素就计算该元素与 target之间的差值，然后到中寻找该差值，如果找到，则返回两个元素在数组 nums 的下标，如果没有找到，则将当前元素存入 HashMap 中 (Key:nums[i],Value:i)。
此处是一次迭代， 在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。
- 时间复杂度：O(n)
- 空间复杂度：O(n)
Java
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
C++
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> record;
for(int i = 0 ; i < nums.size() ; i ++){
int complement = target - nums[i];
if(record.find(complement) != record.end()){
int res[] = {i, record[complement]};
return vector<int>(res, res + 2);
}
record[nums[i]] = i;
}
}
};
总结
Keyword： HashMap 、暴力遍历
对于数组的遍历，首先考虑是否可以借助哈希表存储数组位置、值，实现哈希表的方式有多样，例如字典等。
遍历的1位置，不一定是从头到尾的遍历，可以从第一次遍历位置的左边或者右边进行遍历。
Reference：
[1.] https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/ [2.] https://leetcode-cn.com/problems/two-sum/solution/dong-hua-tu-jie-suan-fa-liang-shu-zhi-he-fu-shi-pi/ [3.] https://leetcode-cn.com/problems/two-sum/solution/jie-suan-fa-1-liang-shu-zhi-he-by-guanpengchn/
