forked from terrytong0876/LintCode-1
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path2 Sum.java
More file actions
executable file
·129 lines (108 loc) · 3.87 KB
/
Copy path2 Sum.java
File metadata and controls
executable file
·129 lines (108 loc) · 3.87 KB
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
M
tutorial:https://www.youtube.com/watch?v=P8zBxoVY1oI&feature=youtu.be
解法1：相对暴力简洁, HashMap<value, index>，找到一个value, 存一个; 若在HashMap里面 match 到结果, 就return HashMap里存的index. O(n) space && time.
解法2：Sort array, two pointer 前后++,--搜索。Sort 用时O(nlogn).
1. 第一步 two pointer 找 value.
2. 注意，要利用额外的空间保留original array， 用来时候找index. (此处不能用HashMap，因为以value 为key，但value可能重复)
O(n) space, O(nlogn) time.
```
/*
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target,
where index1 must be less than index2.
Please note that your returned answers (both index1 and index2) are NOT zero-based.
Example
numbers=[2, 7, 11, 15], target=9
return [1, 2]
Note
You may assume that each input would have exactly one solution
Challenge
Either of the following solutions are acceptable:
O(n) Space, O(nlogn) Time
O(n) Space, O(n) Time
Tags Expand
Two Pointers Sort Hash Table Array Airbnb Facebook
*/
/*
Thoughts:
Using a HashMap, O(n) space and O(n) time.
Thinking process:
Push everything into a HashMap.
Check if one element exist in the HashMap, if so save it. Meanwhile, save the other one.
Trick: after adding into the HashMap, we are looking for the 2nd index first.
Always check (target - current) from the HashMap.
If exist, that means index0 has already been pushed into the HashMap and current value is at index1.
(key, value) = (numbers[i], i)
Note: return index+1 because this is not 0-based.
*/
public class Solution {
//Using HashMap
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return null;
}
int[] rst = new int[2];
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int i = 0; i < numbers.length; i++) {
if (map.containsKey(target - numbers[i])) {
rst[0] = map.get(target - numbers[i]) + 1;
rst[1] = i + 1;
break;
} else {
map.put(numbers[i], i);
}
}
return rst;
}
}
//2. O(n) Space O(nlogn) time
/*
Feels like binary search when looking at O(nlogn)
1. sort
2. loop all number
3. binary search on rest
*/
public class Solution {
public int[] twoSum(int[] numbers, int target) {
if (numbers == null || numbers.length == 0) {
return null;
}
int[] original = new int[numbers.length];
for (int i = 0; i < numbers.length; i++) {
original[i] = numbers[i];
}
Arrays.sort(numbers);
int start = 0;
int end = numbers.length - 1;
int num1 = -1;
int num2 = -1;
while (start != end) {
int sum = numbers[start] + numbers[end];
if (sum == target) {
num1 = numbers[start];
num2 = numbers[end];
break;
}else if (sum < target) {
start++;
} else {
end--;
}
}
//Find the num1,num2 in original array and record the index
int[] rst = new int[2];
rst[0] = -1;
rst[1] = -1;
for (int i = 0; i < original.length; i++) {
if (original[i] == num1 || original[i] == num2) {
if (rst[0] == -1) {
rst[0] = i + 1;
} else {
rst[1] = i + 1;
break;
}
}
}
return rst;
}
}
```