每日一题 2019 - 03 - 05
题目：
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:
1 2 3 4 5 6 7
Given array nums = [-1, 0, 1, 2, -1, -4], A solution set is: [ [-1, 0, 1], [-1, -1, 2] ]
解法：
这个题题意很简单就是让我们找到vector中任意三个数字的和为0的序列，直观的思路就是三重循环解决问题，但是会超时，所以可以换一种思路。
将时间复杂度从$$O(n^3)$$降到$$O(n^2)$$，我们需要减少一层循环的次数，那么我们可以设置两个指针：left = i + 1,right = size - 1，一个从当前坐标的右边一位往后遍历，一个从数组的最后一位往前遍历，如果：
$$nums[i] + nums[left] + nums[right] < 0$$，那么$$left ++$$
$$nums[i] + nums[left] + nums[right] > 0$$，那么$$right ++$$
$$nums[i] + nums[left] + nums[right] = 0$$，那么要求的序列
这里有一个小技巧，可以先对nums先进行排序，那么就一定可以保证求出来的序列一定是从大到小的。
代码：
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
class {public : vector <vector <int >> threeSum(vector <int >& nums) { int size = nums.size(); sort(nums.begin(),nums.end()); vector <vector <int >> test ; if (size <=2 ) { return test ; } for (int i = 0 ; i < size - 2 ; i ++ ) { int left = i + 1 ; int right = size - 1 ; vector <int > temp ; while (left < right){ if (nums[i] + nums[left] + nums[right] < 0 ) { left ++ ; } else if (nums[i] + nums[left] + nums[right] > 0 ) { right -- ; } else { temp.push_back(nums[i]); temp.push_back(nums[left]); temp.push_back(nums[right]); test.push_back(temp); temp.clear(); while (nums[left] == nums[left+1 ] && ( left < size - 2 ) ) { left ++ ; } left ++ ; } } while (nums[i] == nums[i+1 ] && ( i < size - 2 )) { i ++ ; } } return test ; } };
近期评论