欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

leetcode题解-15三数之和

程序员文章站 2022-07-14 17:27:38
...

三数之和:link

1.题目分析

首先想到的是固定两个数最后去确定第三个数,时间复杂度为O(n2logn),最好的方法是固定一个然后使用twoSum的方法去寻找那两个,时间复杂度为O(n2),注意事项为要跳过重复的。

2.示例代码
class Solution {
public:
	vector<vector<int>> threeSum(vector<int>& nums) {
		vector<vector<int>> ret;
		sort(nums.begin(), nums.end());
		for (int i = 0; i < (int)nums.size() - 2; ++i) {
			if (i == 0 || nums[i] != nums[i - 1]) {
				//find the combination
				int lo = i + 1, hi = nums.size() - 1;
				int twoSum = -nums[i];
				while (lo < hi) {
					if (nums[lo] + nums[hi] == twoSum) {
						ret.push_back({ nums[i], nums[lo], nums[hi] });
						while (lo < hi && nums[lo] == nums[lo + 1]) lo++;
						while (lo < hi && nums[hi] == nums[hi - 1]) hi--;
						lo++; hi--;
					}
					else if (nums[lo] + nums[hi] < twoSum) {
						lo++;
					}
					else {
						hi--;
					}
				}
			}
			else {
				//skip the duplications
				continue;
			}
		}
		return ret;
	}
};