LeetCode 15.三数之和 排序+双指针 CC++

LeetCode 15.三数之和 排序+双指针 C/C++

题目链接

1.题目的意思就是找 a ≤ b ≤ c , a + b + c = 0 a leq b leq c,a+b+c=0 a≤b≤c,a+b+c=0 的三元组，为了避免重复我们首先将元素进行排序。
2.然后枚举a，同时要排除a是一样的情况，枚举b时同理。然后使用双指针，即从左往右遍历b同时从右往左寻找c，始终保持b在c的左边且 a + b + c > 0 a+b+c>0 a+b+c>0，后面遍历时，只需要c在当前位置继续往左移即可，因为a不变，b增大，c一定是减小的。最后判断a、b、c是否满足条件。详见代码。
3.时间复杂度：排序 O ( n log ⁡ n ) O(n log n) O(nlogn)，第一重循环 O ( n ) O(n) O(n)，第二重循环因为b往右移的时候，c会左移若干位，平均下来也是左移一位，所以第二重循环也是 O ( n ) O(n) O(n)，故总的时间复杂度为 O ( n 2 ) O(n^2) O(n2)

class Solution {
public:
	vector> threeSum(vector& nums) {
		int n = nums.size();
		sort(nums.begin(),nums.end());//先把数组排序，a,b,c
		vector> ans;
		for(int first = 0;first0&&nums[first]==nums[first-1]) {//排除a是一样的情况，需要和上一次枚举的数不相同
				continue;
			}
			int third = n-1;
			int target = -nums[first];
			//双指针，从左往右遍历b，同时从右往左找c
			for(int second = first+1;secondfirst+1&&nums[second]==nums[second-1]) {
					continue;
				}
				while(secondtarget) {
					third--;
				}
				if(second==third)break;
				if(nums[second]+nums[third]==target) {
					ans.push_back({nums[first],nums[second],nums[third]});
				}
			}
		}
		return ans;
	}
};