知识点
双指针
思路
首先排序,枚举第一个元素,用双指针来得到第二个和第三个元素。实现上如果当前元素和上一个元素相等的话可以跳过,因为当前的所有情况已经在上一个元素处枚举过了。
时间复杂度
AC Code(c++)
#include <vector> class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param nums int整型vector * @param target int整型 * @return int整型vector<vector<>> */ vector<vector<int> > findThreeCows(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); vector<vector<int>> res; int n = nums.size(); vector<int> path; for (int i = 0; i < n; i ++) { if (i and nums[i] == nums[i - 1]) continue; path.push_back(nums[i]); int sum = target - nums[i]; for (int j = i + 1, k = n - 1; j < k; j ++) { if (j > i + 1 and nums[j] == nums[j - 1]) continue; path.push_back(nums[j]); while (j < k and (nums[j] + nums[k] > sum or (k < n - 1 and nums[k] == nums[k + 1]))) k --; if (j < k and nums[j] + nums[k] == sum) { path.push_back(nums[k]); res.push_back(path); path.pop_back(); } path.pop_back(); } path.pop_back(); } return res; } };