Leetcode 第一题 Two Sum

今日发现一好玩的刷题网站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.
Example:

1
2
3
4
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

The return format had been changed to zero-based indices. Please read the above updated description carefully.

实现

总之就是返回一个数组中和为固定值的一组元素的索引(下标),一看到这题目,我就想到了使用递归的方法进行遍历,毕竟第一题,先实现再说。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
private int[] soluArray = new int[2];
public int[] twoSum(int[] nums, int target) {
return search(nums, 0, target);
}
public int[] search(int[] nums, int n, int target) {
if (n != nums.length - 1) {
for (int i = n + 1; i < nums.length; i++) {
if (nums[n] + nums[i] == target) {
soluArray[0] = n;
soluArray[1] = i;
}
}
search(nums, n + 1, target);
}
return soluArray;
}
}

迅速提交代码,程序通过,结果:-(

仅仅超过了8.47%的任务提交,估计很大一部分原因是因为递归调用比较耗时,所以重新想个算法来解决此题:

优化

如果将输入数组进行排序,那么只需在数组中从两头往中间遍历一次,便可判断出符合要求的结果(因为符合的结果只有一组)。

如果要排序,那么必须记录数组最初的位置,否则最后即使计算出结果也没有什么卵用。最初想用map来保存,转念一想虽然可行,但如果遇到重复输入数组,那map就失去作用了,所以改用一个类中有两个成员变量,分别记录元素值和最初位置,代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
public class Solution {
public class A {
private int num;
private int pos;
public A(int num, int pos) {
this.num = num;
this.pos = pos;
}
public int getNum() {
return this.num;
}
public int getPos() {
return this.pos;
}
}
public int[] twoSum(int[] nums, int target) {
A[] a = new A[nums.length];
for (int n = 0; n < nums.length; n++) {
a[n] = new A(nums[n], n);
}
Arrays.sort(a, new Comparator<A>() {
public int compare(A n1, A n2) {
if (n1.getNum() == n2.getNum())
return 0;
if (n1.getNum() > n2.getNum())
return 1;
return -1;
}
});
int i = 0;
int j = nums.length - 1;
int[] result = new int[2];
while (i < j) {
int tmp = a[i].getNum() + a[j].getNum();
if (tmp < target) {
i++;
} else if (tmp > target) {
j--;
}
if (tmp == target) {
result[0] = a[i].getPos();
result[1] = a[j].getPos();
break;
}
}
return result;
}
}

提交运行,也才32%,代码渣表示压力很大呀~~

0%