Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit0460edc

Browse files
refactor 167
1 parent8010a74 commit0460edc

File tree

2 files changed

+95
-20
lines changed

2 files changed

+95
-20
lines changed
Lines changed: 57 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -1,27 +1,13 @@
11
packagecom.fishercoder.solutions;
22

3-
/**
4-
* 167. Two Sum II - Input array is sorted
5-
6-
Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
7-
8-
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.
9-
10-
Note:
11-
12-
Your returned answers (both index1 and index2) are not zero-based.
13-
You may assume that each input would have exactly one solution and you may not use the same element twice.
14-
15-
Example:
16-
17-
Input: numbers = [2,7,11,15], target = 9
18-
Output: [1,2]
19-
Explanation: The sum of 2 and 7 is 9. Therefore index1 = 1, index2 = 2.
20-
21-
*/
3+
importjava.util.Arrays;
224

235
publicclass_167 {
246
publicstaticclassSolution1 {
7+
/**
8+
* This is an amazing solution!
9+
* Time: O(logn)
10+
*/
2511
publicint[]twoSum(int[]numbers,inttarget) {
2612
intleft =0;
2713
intright =numbers.length -1;
@@ -38,4 +24,56 @@ public int[] twoSum(int[] numbers, int target) {
3824
returnnewint[]{-1, -1};
3925
}
4026
}
27+
28+
publicstaticclassSolution2 {
29+
/**
30+
* Time: O(nlogn)
31+
*/
32+
publicint[]twoSum(int[]numbers,inttarget) {
33+
for (inti =0;i <numbers.length -1;i++) {
34+
intindex =exists(Arrays.copyOfRange(numbers,i +1,numbers.length),target -numbers[i]);
35+
if (index >=0) {
36+
returnnewint[]{i +1,index +2 +i};
37+
}
38+
}
39+
returnnull;
40+
}
41+
42+
privateintexists(int[]nums,inttarget) {
43+
intleft =0;
44+
intright =nums.length -1;
45+
while (left <right) {
46+
intmid =left + (right -left) /2;
47+
if (nums[mid] ==target) {
48+
returnmid;
49+
}elseif (nums[mid] <target) {
50+
left =mid +1;
51+
}else {
52+
right =mid -1;
53+
}
54+
}
55+
returnnums[left] ==target ?left : (right >=0 &&nums[right] ==target) ?right : -1;
56+
}
57+
}
58+
59+
publicstaticclassSolution3 {
60+
/**
61+
* Time: O(nlogn)
62+
*/
63+
publicint[]twoSum(int[]numbers,inttarget) {
64+
for (inti =0;i <numbers.length -1;i++) {
65+
int[]ans =newint[2];
66+
ans[0] =i +1;
67+
intindex =Arrays.binarySearch(Arrays.copyOfRange(numbers,i,numbers.length),target -numbers[i]);
68+
if (index >0) {
69+
ans[1] =index +1 +i;
70+
returnans;
71+
}elseif (index ==0) {
72+
ans[1] =index +2 +i;
73+
returnans;
74+
}
75+
}
76+
returnnull;
77+
}
78+
}
4179
}

‎src/test/java/com/fishercoder/_167Test.java

Lines changed: 38 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,18 +8,55 @@
88

99
publicclass_167Test {
1010
privatestatic_167.Solution1solution1;
11+
privatestatic_167.Solution2solution2;
12+
privatestatic_167.Solution3solution3;
1113
privatestaticint[]numbers;
1214
privatestaticint[]expected;
15+
privateinttarget;
1316

1417
@BeforeClass
1518
publicstaticvoidsetup() {
1619
solution1 =new_167.Solution1();
20+
solution2 =new_167.Solution2();
21+
solution3 =new_167.Solution3();
1722
}
1823

1924
@Test
2025
publicvoidtest1() {
2126
numbers =newint[]{-3,3,4,90};
2227
expected =newint[]{1,2};
23-
assertArrayEquals(expected,solution1.twoSum(numbers,0));
28+
target =0;
29+
assertArrayEquals(expected,solution1.twoSum(numbers,target));
30+
assertArrayEquals(expected,solution2.twoSum(numbers,target));
31+
assertArrayEquals(expected,solution3.twoSum(numbers,target));
32+
}
33+
34+
@Test
35+
publicvoidtest2() {
36+
expected =newint[]{2,3};
37+
target =100;
38+
assertArrayEquals(expected,solution1.twoSum(newint[]{5,25,75},target));
39+
assertArrayEquals(expected,solution2.twoSum(newint[]{5,25,75},target));
40+
assertArrayEquals(expected,solution3.twoSum(newint[]{5,25,75},target));
41+
}
42+
43+
@Test
44+
publicvoidtest3() {
45+
numbers =newint[]{1,2,3,4,4,9,56,90};
46+
expected =newint[]{4,5};
47+
target =8;
48+
assertArrayEquals(expected,solution1.twoSum(numbers,target));
49+
assertArrayEquals(expected,solution2.twoSum(numbers,target));
50+
assertArrayEquals(expected,solution3.twoSum(numbers,target));
51+
}
52+
53+
@Test
54+
publicvoidtest4() {
55+
numbers =newint[]{2,3,4};
56+
expected =newint[]{1,3};
57+
target =6;
58+
assertArrayEquals(expected,solution1.twoSum(numbers,target));
59+
assertArrayEquals(expected,solution2.twoSum(numbers,target));
60+
assertArrayEquals(expected,solution3.twoSum(numbers,target));
2461
}
2562
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp