题解 | #找到满足条件的牛群组合# 双指针

知识点

双指针

思路

首先排序，枚举第一个元素，用双指针来得到第二个和第三个元素。实现上如果当前元素和上一个元素相等的话可以跳过，因为当前的所有情况已经在上一个元素处枚举过了。

时间复杂度

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;
    }
};