LeetCode num016

Problem

3Sum Closest
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.

1
2
3
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).

Solution

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
class Solution {
public:
int threeSumClosest(vector<int> &num, int target)
{

sort(num.begin(), num.end());
int i = 0, min, temp, first;
min = num[0] + num[1] + num[2] - target;
while (num.size() >= 3)
{
first = num[0];
num.erase(num.begin());
temp = twoSumClosest(num, target - first);
if (abs(temp + first - target) < abs(min))
{
min = temp + first - target;
}
}
return min + target;
}
int twoSumClosest(vector<int> num, int target)
{

int i, j, minBig, minSmall, markBig = 0, markSmall = 0;
for (i = 0, j = num.size() - 1; i < j;)
{
if (num[i] + num[j] == target)
{
return target;
}
else if (num[i] + num[j] > target)
{
if (markBig == 0)
{
minBig = num[i] + num[j];
markBig = 1;
}
else
{
minBig = minBig < (num[i] + num[j]) ? minBig : (num[i] + num[j]);
}
j--;
}
else
{
if (markSmall == 0)
{
minSmall = num[i] + num[j];
markSmall = 1;
}
else
{
minSmall = minSmall > (num[i] + num[j]) ? minSmall : (num[i] + num[j]);
}
i++;
}
}
if (markSmall == 0)
{
return minBig;
}
else if (markBig == 0)
{
return minSmall;
}
else
{
return (target - minSmall) < (minBig - target) ? minSmall : minBig;
}
}
};

Comment

  1. 写代码要细致;
  2. 不要迁就代码,尽量不要黏贴别的代码进行改;
  3. 要有勇气放弃代码,从头写;
  4. 本题时间复杂度为O(n^2)。

LeetCode num015

Problem

3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:
Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
The solution set must not contain duplicate triplets.

1
2
3
4
5
For example, given array S = {-1 0 1 2 -1 -4},

A solution set is:
(-1, 0, 1)
(-1, -1, 2)

Solution

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
class Solution {
public:
vector<vector<int> > threeSum(vector<int> &num) {
sort(num.begin(), num.end());
vector<vector<int>> result, get;
vector<int> fine;
int target;
int i, j, k, mark;
for (i = 0; num.size() >= 3; i++)
{
target = 0 - num[0];
if (i >= 1 && target == mark)
{
num.erase(num.begin());
continue;
}
mark = target;
num.erase(num.begin());
get = twoSum(num, target);
for (k = 0; k < get.size(); k++)
{
fine = get[k];
result.push_back(fine);
}
}
return result;
}
vector<vector<int> > twoSum(vector<int> &num, int target)
{
vector<int> fine;
vector<vector<int> > result;
int sum, count1 = 0, count2 = 0, mark1, mark2;
vector<int>::iterator it1 = num.begin(), it2 = num.end() - 1;
for (it1 = num.begin(), it2 = num.end() - 1; it1 < it2;)
{
if (count1 >= 1 && *it1 == mark1)
{
it1++;
continue;
}
else if (count2 >= 1 && *it2 == mark2)
{
it2--;
continue;
}
sum = *it1 + *it2;
if (sum == target)
{
fine.push_back(0 - target);
fine.push_back(*it1);
fine.push_back(*it2);
result.push_back(fine);
fine.clear();
mark1 = *it1;
mark2 = *it2;
it1++;
it2--;
count1++;
count2++;
}
else if (sum < target)
{
mark1 = *it1;
it1++;
count1++;
}
else
{
mark2 = *it2;
it2--;
count2++;
}

}
return result;
}
};

Comment

  1. 代码不够简洁;
  2. 类似两个数的和;
  3. 复杂度能够到O(n^2)。