题目:
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.
思路:
1.两个指针遍历,用bin_search查询是否存在-a-b(time exceeded)
2.遍历一次,用front和back夹逼查询 https://leetcode.com/discuss/23595/share-my-solution-around-50ms-with-explanation-and-comments
都首先用std:sort()进行排序
代码 思路2 C++:
class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { vector<vector<int>> solve; if (nums.size() < 3) return solve; sort(nums.begin(), nums.end()); for (int ptr_1 = 0; ptr_1 < nums.size() - 2;ptr_1++ ) { int target = -nums[ptr_1]; int front = ptr_1 + 1; int back = nums.size() - 1; while (front < back) { int sum = nums[front] + nums[back]; if (target > sum) front++; else if (target < sum) back--; else{ vector<int> ans(3,0); ans[0] = nums[ptr_1]; ans[1] = nums[front]; ans[2] = nums[back]; solve.push_back(ans); while (front < back && nums[front] == ans[1]) front++; while (front < back && nums[back] == ans[2]) { back--; } } } while (ptr_1 + 1 < nums.size() - 2 && nums[ptr_1] == nums[ptr_1 + 1]) { ptr_1++; } } return solve; } };
原文:http://www.cnblogs.com/gavinxing/p/5299437.html