forked from algorithm010/algorithm010
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathLC167_two_sum_ii.java
More file actions
60 lines (54 loc) · 1.61 KB
/
LC167_two_sum_ii.java
File metadata and controls
60 lines (54 loc) · 1.61 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
package Week06;
import java.util.HashMap;
import java.util.Map;
public class LC167_two_sum_ii {
//HashMap
public int[] twoSum(int[] numbers, int target) {
Map<Integer,Integer> map = new HashMap<Integer,Integer>();
for(int i=0;i<numbers.length;i++){
Integer val = target - numbers[i];
if (map.containsKey(val)){
return new int[]{map.get(val)+1,i+1};
}
else{
map.put(numbers[i],i);
}
}
return null;
}
//binary search
public int[] twoSum_2(int[] numbers, int target) {
for (int i = 0; i < numbers.length; ++i) {
int low = i + 1, high = numbers.length - 1;
while (low <= high) {
int mid = (high - low) / 2 + low;
if (numbers[mid] == target - numbers[i]) {
return new int[]{i + 1, mid + 1};
} else if (numbers[mid] > target - numbers[i]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return new int[]{-1, -1};
}
//double points
public int[] twoSum_3(int[] numbers, int target) {
int left = 0;
int right = numbers.length -1;
while (left<right){
int val = numbers[left]+numbers[right];
if (val == target){
return new int[]{left+1,right+1};
}
else if (val < target){
left++;
}
else {
right--;
}
}
return null;
}
}