LeetCode

Two Sum

原题:

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:

翻译:

给定一个整数数组,返回两个数字的索引,使它们相加到一个特定的目标。
你可以假设每个输入都只有一个解决方案,而你可能不会使用相同的元素两次。

解决思路:
第一种可以用两层循环(时间复杂度O(n^2)),实现代码:

1
2
3
4
5
6
7
8
9
public int[] twoSum1(int[] tmp, int target) {
for (int i = 0; i < tmp.length; i++){
for (int j = i + 1; j < tmp.length; j++){
if (tmp[i] + tmp[j] == target)
return new int[]{i, j};
}
}
throw new IllegalArgumentException("don't have two sum equals target");
}

第二种可以定义一个map然后把数组的值作为key,索引作为value存到map中,循环数组,每次循环用目标值减去该值,用结果作为key去map中查找,找到了返回索引数组,没找到把该次和循环的值和索引作为key和value存入map中,直到找到结果。(时间复杂度O(n))实现:

1
2
3
4
5
6
7
8
9
10
11
public int[] twoSum(int[] tmp, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i<tmp.length; i++){
int m = target - tmp[i];
if (map.containsKey(m)) {
return new int[] { map.get(m), i };
}
map.put(tmp[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}

python实现

最近也在学习python,附上python的实现(第二种方案):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class :
def twoSum(self, nums, target):
map = {}
i = 0
for x in nums:
if target - x in map:
return i,map[target - x]
print str(x) + " " + str(i)
map[x] = i
print map
i += 1
return
if __name__=="__main__":
a = [5, 4, 9, 3, 7]
solution = Solution()
print solution.twoSum(a, 10)