FilesExpand file tree

 master

/

ThreeSumClosest.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

145 lines (121 loc) · 4.73 KB

 master

/

ThreeSumClosest.java

Copy path

Top

File metadata and controls

• Code
• Blame

145 lines (121 loc) · 4.73 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

import java.util.Arrays;

/**

* Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target.

* Return the sum of the three integers. You may assume that each input would have exactly one solution.

* For example, given array S = {-1 2 1 -4}, and target = 1.

* The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

* <p/>

* The solution is to use two nested loops to enumerate the combination of num[i], num[j],

* and then use binary search to locate the numbers which may have the closest distance with the target.

* The complexity of this algorithm is O(n^2*logn).

*/

public class ThreeSumClosest {

public static void main(String[] args) {

int[] a = new int[]{-1, 2, 1, -4};

int target = 1;

int[] result = threeSumClosest(a, target);

System.out.println(Arrays.toString(result));

int[] result1 = threeSumClosest1(a, target);

System.out.println(Arrays.toString(result1));

}

public static int[] threeSumClosest(int[] a, int target) {

int[] result = new int[3];

if (a.length < 3)

return result;

Arrays.sort(a);

int min_distance = Integer.MAX_VALUE;

for (int i = 0; i < a.length - 2; i++) { // extra two element needed, so i<a.length-2

for (int j = i + 1; j < a.length - 1; j++) { // extra one element needed, so j<a.length-1

int val = target - a[i] - a[j];

int begin = j + 1, end = a.length - 1, mid, sum;

int[] temp = new int[3];

while (begin <= end) {

mid = (begin + end) / 2;

if (a[mid] == val) {

result[0] = a[i];

result[1] = a[j];

result[2] = a[mid];

return result;

} else if (a[mid] < val) {

begin = mid + 1;

} else {

end = mid - 1;

}

}

if (begin > a.length - 1) {

sum = a[i] + a[j] + a[end];

temp[0] = a[i];

temp[1] = a[j];

temp[2] = a[end];

} else if (end < j + 1) {

sum = a[i] + a[j] + a[begin];

temp[0] = a[i];

temp[1] = a[j];

temp[2] = a[begin];

} else {

int d1 = a[i] + a[j] + a[begin];

int d2 = a[i] + a[j] + a[end];

int d1_distance = Math.abs(d1 - target);

int d2_distance = Math.abs(d2 - target);

if (d1_distance < d2_distance) {

sum = d1;

temp[0] = a[i];

temp[1] = a[j];

temp[2] = a[begin];

} else {

sum = d2;

temp[0] = a[i];

temp[1] = a[j];

temp[2] = a[end];

}

}

if (Math.abs(sum - target) < min_distance) {

min_distance = Math.abs(sum - target);

result = temp.clone();

}

}

}

return result;

}

// non binary search O(n^3)

public static int[] threeSumClosest1(int[] a, int target) {

int[] result = new int[3];

if (a.length < 3)

return result;

Arrays.sort(a);

int min_distance = Integer.MAX_VALUE;

int x, y, z, sum, temp_distance;

for (int i = 0; i < a.length - 2; i++) {

x = a[i];

for (int j = i + 1, k = a.length - 1; j < k; ) {

y = a[j];

z = a[k];

sum = x + y + z;

temp_distance = Math.abs(sum - target);

if (sum < target) {

if (temp_distance < min_distance) {

min_distance = temp_distance;

result[0] = x;

result[1] = y;

result[2] = z;

}

j++;

} else if (sum > target) {

if (temp_distance < min_distance) {

min_distance = temp_distance;

result[0] = x;

result[1] = y;

result[2] = z;

}

k--;

} else {

result[0] = x;

result[1] = y;

result[2] = z;

return result;

}

}

}

return result;

}

}