Skip to content

Commit 53953d5

Browse files
xiaoningningxiaoningning
committed
three sum closest
1 parent 11680d3 commit 53953d5

3 files changed

Lines changed: 154 additions & 2 deletions

File tree

‎PuzzleCoding/src/DecodeNumber.java‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -23,12 +23,19 @@ public static void main(String[] args) {
2323

2424
public static void decodeNumber(String s) {
2525
int len = s.length();
26+
27+
if(len == 0){
28+
System.out.println("empty string");
29+
return;
30+
}
31+
2632
for (int i = 0; i < len; i++) {
2733
if (!((s.charAt(i) - '0') <= 9) && !(('9' - s.charAt(i)) >= 0)) {
2834
System.out.println(s + " is not number.");
2935
return;
3036
}
3137
}
38+
3239
int[] ways = new int[len];
3340
ways[0] = (s.charAt(0) == '0') ? 0 : 1;
3441
for (int i = 1; i < len; i++) {

‎PuzzleCoding/src/ThreeSumClosest.java‎

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,145 @@
1+
import java.util.Arrays;
2+
3+
/**
4+
* Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.
5+
* Return the sum of the three integers. You may assume that each input would have exactly one solution.
6+
* For example, given array S = {-1 2 1 -4}, and target = 1.
7+
* The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
8+
* <p/>
9+
* The solution is to use two nested loops to enumerate the combination of num[i], num[j],
10+
* and then use binary search to locate the numbers which may have the closest distance with the target.
11+
* The complexity of this algorithm is O(n^2 logn).
12+
*/
13+
public class ThreeSumClosest {
14+
public static void main(String[] args) {
15+
int[] a = new int[]{-1, 2, 1, -4};
16+
int target = 1;
17+
18+
int[] result = threeSumClosest(a, target);
19+
System.out.println(Arrays.toString(result));
20+
21+
int[] result1 = threeSumClosest1(a, target);
22+
System.out.println(Arrays.toString(result1));
23+
}
24+
25+
public static int[] threeSumClosest(int[] a, int target) {
26+
int[] result = new int[3];
27+
28+
if (a.length < 3)
29+
return result;
30+
31+
Arrays.sort(a);
32+
33+
int min_distance = Integer.MAX_VALUE;
34+
35+
for (int i = 0; i < a.length - 2; i++) { // extra two element needed, so i<a.length-2
36+
for (int j = i + 1; j < a.length - 1; j++) { // extra one element needed, so j<a.length-1
37+
int val = target - a[i] - a[j];
38+
int begin = j + 1, end = a.length - 1, mid, sum;
39+
int[] temp = new int[3];
40+
while (begin <= end) {
41+
mid = (begin + end) / 2;
42+
43+
if (a[mid] == val) {
44+
result[0] = a[i];
45+
result[1] = a[j];
46+
result[2] = a[mid];
47+
return result;
48+
} else if (a[mid] < val) {
49+
begin = mid + 1;
50+
} else {
51+
end = mid - 1;
52+
}
53+
}
54+
if (begin > a.length - 1) {
55+
sum = a[i] + a[j] + a[end];
56+
temp[0] = a[i];
57+
temp[1] = a[j];
58+
temp[2] = a[end];
59+
} else if (end < j + 1) {
60+
sum = a[i] + a[j] + a[begin];
61+
temp[0] = a[i];
62+
temp[1] = a[j];
63+
temp[2] = a[begin];
64+
} else {
65+
int d1 = a[i] + a[j] + a[begin];
66+
int d2 = a[i] + a[j] + a[end];
67+
68+
int d1_distance = Math.abs(d1 - target);
69+
int d2_distance = Math.abs(d2 - target);
70+
if (d1_distance < d2_distance) {
71+
sum = d1;
72+
temp[0] = a[i];
73+
temp[1] = a[j];
74+
temp[2] = a[begin];
75+
76+
} else {
77+
sum = d2;
78+
temp[0] = a[i];
79+
temp[1] = a[j];
80+
temp[2] = a[end];
81+
82+
}
83+
84+
}
85+
if (Math.abs(sum - target) < min_distance) {
86+
min_distance = Math.abs(sum - target);
87+
88+
result = temp.clone();
89+
}
90+
91+
}
92+
}
93+
return result;
94+
}
95+
96+
// non binary search
97+
public static int[] threeSumClosest1(int[] a, int target) {
98+
int[] result = new int[3];
99+
100+
if (a.length < 3)
101+
return result;
102+
103+
Arrays.sort(a);
104+
105+
int min_distance = Integer.MAX_VALUE;
106+
int x, y, z, sum, temp_distance;
107+
for (int i = 0; i < a.length - 2; i++) {
108+
x = a[i];
109+
for (int j = i + 1, k = a.length-1; j < k; ) {
110+
y = a[j];
111+
z = a[k];
112+
sum = x+y+z;
113+
temp_distance = Math.abs(sum-target);
114+
if(sum < target){
115+
116+
if(temp_distance < min_distance){
117+
min_distance = temp_distance;
118+
result[0] = x;
119+
result[1] = y;
120+
result[2] = z;
121+
}
122+
j++;
123+
} else if(sum > target){
124+
if(temp_distance < min_distance){
125+
min_distance = temp_distance;
126+
result[0] = x;
127+
result[1] = y;
128+
result[2] = z;
129+
}
130+
k--;
131+
}else {
132+
result[0] = x;
133+
result[1] = y;
134+
result[2] = z;
135+
return result;
136+
137+
}
138+
139+
}
140+
}
141+
142+
return result;
143+
144+
}
145+
}

‎sumZero/src/nw/SumZero.java‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -127,12 +127,12 @@ public static void sum3Zero1(int[] list) {
127127
return;
128128
}
129129

130-
for (int i = 0; i < list.length; ++i) {
130+
for (int i = 0; i < list.length-2; ++i) {
131131
if (list[i] > 0) {
132132
System.out.println("not found");
133133
break;
134134
}
135-
for (int j = i + 1; j < list.length; ++j) {
135+
for (int j = i + 1; j < list.length-1; ++j) {
136136
int tmp = (list[i] + list[j]) * -1;
137137

138138
int s = j + 1, e = list.length - 1;

0 commit comments

Comments
 (0)