-
Notifications
You must be signed in to change notification settings - Fork 0
/
TwoSum2.java
73 lines (59 loc) · 1.45 KB
/
TwoSum2.java
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
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
//https://leetcode.com/problems/two-sum/ 最好的解法。
//step1 : copy an array, and sort it using quick sort, O(nlogn)
//step2 : using start and end points to find a, b which satifys a+b==target, O(n)
//step3 : find the index of a, b from origin array, O(n)
import java.util.Arrays;
public class TwoSum2 {
public int[] twoSum(int[] nums, int target) {
if(null == nums) return null;
int[] res = new int[2];
int[] nums2 = Arrays.copyOf(nums, nums.length);
Arrays.sort(nums2);
//find sum factor a and b
int a = 0; int b = 0;
int start = 0; int end = nums.length - 1;
while (start < end) {
if (nums2[start] + nums2[end] < target) {
start++;
} else if(nums2[start] + nums2[end] > target) {
end--;
} else {
a = nums2[start]; b = nums2[end];
break;
}
}
//find a index in array nums
for (int i = 0; i < nums.length; i++) {
if (a == nums[i]) {
res[0] = i;
break;
}
}
// may a=b
if (a == b) {
for (int j = res[0]; j < nums.length; j++) {
if (b == nums[j]) {
res[1] = j;
break;
}
}
} else {
for (int j = 0; j < nums.length; j++) {
if (b == nums[j]) {
res[1] = j;
break;
}
}
}
return res;
}
public static void main(String args[]) {
TwoSum2 obj = new TwoSum2();
int[] num = {2, 7, 11, 15};
int target = 9;
System.out.print(target);
int[] res = obj.twoSum(num, target);
System.out.print(res);
System.out.print(obj.twoSum(num, target));
}
}