Leetcode 第一题 Two Sum

发表于 | | 阅读次数:
字数统计: 668 | 阅读时长 ≈ 3

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