今天看到某位大神的一句话，就作为开篇寄语吧。平生不识TwoSum,刷尽LeetCode也枉然。第一题是一道Easy的练手题。
题目
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.
Example:
Given nums = [2, 7, 11, 15], target = 9,Because nums[0] + nums[1] = 2 + 7 = 9,return [0,1].
翻译
给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。
你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用
注意审题
1. 假定每组输入，只有一种解法，也就是返回数组是唯一的。
2. 相同的元素是不能被使用两次的
解题
解法1
因为是简单类型，所以拿过来不经过太多思考就可以给出一个最简单思路，循环遍历数据两遍，取出数字相加和目标数字比较即可得出答案。
Java Solution 1:
class Solution {
public int[] twoSum(int[] nums, int target) {
for(int i =0 ; i< nums.length; i++){
int numOne = nums[i];
for( int j=i+1; j< nums.length; j++){
if (j == i)
break;
if (numOne + nums[j] == target)
return new int[]{i,j};
}
}
return new int[]{};
}
}
这种解题思路简单直接，但考虑到时间复杂度的话是O(n^2). 可以看到收到的报告结果。
image
Java Solution 2:
一般的思路是降低时间复杂度，就是要从空间复杂度下手，多站内存，少循环的思路。用HashMap来维护数据和Index之间的关系，从而将时间复杂度降到 O(n)
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> indexMap = new HashMap<Integer,Integer>();
for (int i=0; i< nums.length; i++) {
Integer index = indexMap.get(target - nums[i]);
if (index != null)
return new int[]{index, i};
else
indexMap.put(nums[i], i);
}
return new int[]{};
}
}
这样提交后的统计结果，时间成本下降了许多
image
Phython Solution 3:
这个solution 纯是自己胡乱思考出来，说白了，把每个数组里的数字都扩展成一个 和 原数组等长的 1 * m 的数组， 需要m 个，然后相加， 再从结果中找出是目标和数字的index 就完成了。由于LeetCode 不支持numpy 所以没能提交
import numpy as np
class Solution:
def twoSum(self, nums, target):
#原数组
numsm = np.array(nums)
for num in nums:
index1 = nums.index(num)
#每个数据新生成的 1 * m 数组
matrix = np.ones(nums.__len__()) * num
a = matrix + numsm
#get target index if exists
if np.argwhere(a == target).size > 0:
index2 = np.argwhere(a == target)[0][0]
if index1 != index2:
return [index1, index2]
return []
网友评论