leetcode/4sum(AC).cpp at master · M-orpheus/leetcode · GitHub

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
// 1AC, excellent!
// #define MY_MAIN
#include <algorithm>
#include <cstdio>
#include <map>
#include <string>
#include <vector>
using namespace std;

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
		int n;
		int a, b, c, d;
		int s;
		vector<int> vtmp;
		char str[100];

		for (n = 0; n < (int)result.size(); ++n) {
			result[n].clear();
		}
		result.clear();
		signs.clear();
		vtmp.clear();

		// sort the array first
		sort(num.begin(), num.end());
		n = (int)num.size();
		for (a = 0; a < n; ++a) {
			for (d = a + 3; d < n; ++d) {
				if (num[a] + num[d - 2] + num[d - 1] + num[d] < target) {
					// too small
					continue;
				}
				if (num[a] + num[a + 1] + num[a + 2] + num[d] > target) {
					// too large
					continue;
				}

				b = a + 1;
				c = d - 1;
				s = target - num[a] - num[d];
				while (true) {
					if (b >= c) {
						// edge is crossed
						break;
					}
					if (num[b] + num[c] < s) {
						++b;
					} else if (num[b] + num[c] > s) {
						--c;
					} else {
						str[0] = 0;
						// create a digital sign to detect duplicates.
						sprintf(str, "%d%d%d%d", num[a], num[b], num[c], num[d]);
						string ss = string(str);
						if (signs.find(ss) == signs.end()) {
							signs[ss] = 1;
							vtmp.clear();
							vtmp.push_back(num[a]);
							vtmp.push_back(num[b]);
							vtmp.push_back(num[c]);
							vtmp.push_back(num[d]);
							result.push_back(vtmp);
						}
						++b;
						--c;
					}
				}
			}
		}

		return result;
    }
private:
	vector<vector<int> > result;
	map<string, int> signs;
};

#ifdef MY_MAIN
int main()
{
	int target;
	vector<int> num;
	int n;
	int tmp;
	Solution solution;
	vector<vector<int> > result;
	int i, j;

	while (scanf("%d%d", &n, &target) == 2) {
		num.clear();
		for (i = 0; i < n; ++i) {
			scanf("%d", &tmp);
			num.push_back(tmp);
		}
		result = solution.fourSum(num, target);
		printf("A solution set is:\n");
		for (i = 0; i < (int)result.size(); ++i) {
			printf("(%d", result[i][0]);
			for (j = 1; j < 4; ++j) {
				printf(", %d", result[i][j]);
			}
			printf(")\n");
		}
		printf("\n");
	}

	return 0;
}
#endif