LeetCode-Two Sum

最近准备开始刷一些 LeetCode 的题目,从简单的开始,第一题是 Two Sum。

https://leetcode.com/problems/two-sum/

前一阵问小伙伴,被告知 C#在 LeetCode 上不是很好用,所以这次就选了 Python 作为实现语言。

思路一:最脑残的方法,直接表达题目的意思

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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(len(nums)):
if i==j:
continue;
if nums[i]+nums[j]==target:
return [i,j]

O(n^2)的效率,有时候能过,不过在运行一些算例的时候会超时,上次成功用了 725ms 思路二:改进了一下循环,减少了很多无谓的比较

1
2
3
4
5
6
7
8
9
10
11
12
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 nums[i]+nums[j]==target:
return [i,j]

修改以后,效果也还不错,用时 569ms 思路三:利用 Python 的哈希表(Dict)数据结构

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
sumDict={}
for i in xrange(len(nums)):
n=nums[i]
if target-n in sumDict:
return [sumDict[target-n],i]
sumDict[n]=i

这一种应该算是我能想到的最简单的算法了,在看了一些网上的答案以后,感觉都是实现了一个哈希表,表现的结果应该大同小异。最终用时 408ms。

改用 Java 重写

继续 Python 的思路,双层 for 循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ret=new int[2];
for(int i=0;i<nums.length;i++){
for(int j=i+1;j<nums.length;j++){
if(nums[i]+nums[j]==target){
ret[0]=i;
ret[1]=j;
break;
}
}
}
return ret;
}
}

使用 Java 的哈希表改成单层 for 循环:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> hm=new HashMap<>();
for(int i=0;i<nums.length;i++){
int minu=target-nums[i];
if(hm.containsKey(minu)){
return new int[] {i,hm.get(minu)};
}else{
hm.put(nums[i],i);
}
}
throw new IllegalArgumentException("No solution");
}
}

运行时间为 5ms 左右。