Given an array nums of n integers, are there elements a, b, c in nums 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.
Example:
Given array nums = [-1, 0, 1, 2, -1, -4],
A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
思路1 暴力穷举 o(n3)
思路2 a+b+c=0 c=-b-a 穷举找-a-b，然后找数组里有没有c,(用set,复杂度 o(1)) ->o(n2)
// 思路2 效率低，主要有去重复的问题,（未解决） vector<vector<int>> threeSum2(vector<int>& nums) { // 放入set中 std::map<int, bool> setNums; std::set<vector<int>> result; for (auto num : nums) { setNums.insert(std::make_pair(num, false)); } for (int a = 0; a < nums.size() - 1; a++) { for (int b = a + 1; b < nums.size(); b++) { int tempC = -nums[a] - nums[b]; setNums.at(nums[a]) = true; setNums.at(nums[b]) = true; // 说明这是ab了不会是c了 auto iterator = setNums.find(tempC); if (iterator != setNums.end() && setNums.at(tempC) == false) { vector<int> temp = { nums[a], nums[b], tempC }; std::sort(temp.begin(), temp.end()); result.insert(temp); } setNums.at(nums[a]) = false; setNums.at(nums[b]) = false; } } vector<vector<int>> result2(result.begin(), result.end()); return result2; }思路3 先排序在找 sort :NlogN 块排 枚举a,b从后面一堆数的第一个开始，c从最后一个开始 （O（n))
A+B+C<0 则B往右移A+B+C>0 则C往左移一格 一直移到B=C,看有没有找到一个等于0的 O(N) 时间复杂度 O（N2） vector<vector<int>> threeSum(vector<int>& nums) { std::vector<vector<int>> result; if (nums.empty()) { return result; } std::size_t n_size = nums.size(); std::sort(nums.begin(), nums.end()); for (int i = 0; i < n_size; ++i) { // all numbers from now on will be greater than 0, no point in continuing if (nums[i] > 0) break; // we have seen this number & combo before; skip 去重 if (i > 0 and nums[i] == nums[i-1]) continue; int left = i+1, right = n_size - 1; while (left < right) { int sum = nums[i] + nums[left] + nums[right]; if (sum < 0) { ++left; } else if (sum > 0) { --right; } else { result.push_back({nums[i], nums[left], nums[right]}); int last_left = nums[left], last_right = nums[right]; // we have seen this number & combo before; skip 去重 while (left < right && nums[left] == last_left) ++left; while (left < right && nums[right] == last_right) --right; } } } return result; }