Description

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: The solution set must not contain duplicate triplets. For example: given array S = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1],  [-1, -1, 2] ]

Solution

对于三个数之和a + b + c = 0形式转化为a + b = -c, 从而规约为week_1的两数和问题。

解决问题的思路如下：

① 首先对输入的vector数组按从小到大进行排序, 时间复杂度为O(nlogn)。

② 对输入进行进一步预处理, 可以在O(n)的时间复杂度内对数组元素进行去重, 并对出现次数进行统计。

③ 为后续算法中快速对相应元素进行检索, 以(元素值, 出现次数)为键值对在map中进行存储。

④ 对去重的有序结构体数组进行二重遍历:

i. 第一重循环对元素c进行选定, 以-c为两数和target, 同时在map中对相应元素的计数器减1。

ii. 第二重循环从第一重循环的下标开始遍历, 选定当前元素current, 同时对complete = target - current进行计算。对current计数器进行检查, 若计数器大于0, 且current <= complete，进一步处理如下：

a. current计数器减1。

b. 对map进行检查, 如果complete存在于map且相应的计数器大于0, 将[-target, current, complete]加入结果数组

c. current计数器加1.

iii. 元素c的计数器加1, 返回i。

解释：

i. 第二重循环之所以要从第一重循环下标开始, 且current计数器要大于0, 是因为输入中可能存在[0, 0, 0]的情况, 其在新结构体数组中仅对应{0, 3}一项。

ii. 要求current <= complete是防止相同的三元组被重复存储, 如输入[-1, 0, 1], -1为c元素, 0为current 与 0为c元素, 1为target这两种情况对应的三元组是相同的。由于数组从小到大排序, 满足current > complete的情况(c, a, b)必然在先遍历到b的时候，即以b为current时就以(c, b, a)的形式存入result返回值数组了。 

整个算法的实现如下：

//适合处理的结构体 struct element { int val; int count; //构造函数 element(int _val, int _count) { val = _val; count = _count; } }; //将threeSum:a + b + c = 0转化为a + b以-c为target的twoSum问题 vector<vector<int>> threeSum(vector<int>& nums) { //首先对nums进行排序 sort(nums.begin(), nums.end()); //对相同元素进行合并，并且对重复次数进行统计 vector<element> input; //初始化第一个元素 element begin(nums[0], 1); input.push_back(begin); //计数器 int inputIndex = 0, numsIndex = 1; while (numsIndex < nums.size()) { if (nums[numsIndex] == nums[numsIndex - 1]) input[inputIndex].count++; else { element newElement(nums[numsIndex], 1); input.push_back(newElement); inputIndex++; } numsIndex++; } //初始化Map map<int, int> countMap; for (int i = 0; i < input.size(); i++) countMap[input[i].val] = input[i].count; //返回值 vector<vector<int>> result; //处理 for (int i = 0; i < input.size(); i++) { int target = -input[i].val; //计数器-1 countMap[-target]--; //TwoSum问题 for (int j = i; j < input.size(); j++) { int current = input[j].val; int complete = target - current; if (countMap[current] > 0 && current <= complete) { //计数器-1 countMap[current]--; if (countMap.find(complete) != countMap.end() && countMap[complete] >= 1) { vector<int> triplet(3); triplet[0] = -target; triplet[1] = current; triplet[2] = complete; result.push_back(triplet); } countMap[current]++; } } countMap[-target]++; } return result; }

在leetcode上提交结果如下：

虽然Ac了, 但是可以看到可以说是非常拙劣的算法了, 希望有时间可以继续思考学习和改进。