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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

本题考察的知识点是数组的遍历和查找，以及对组合的判断和记录。

题目解答方法的文字分析

首先，我们需要找到满足条件的三只牛的组合，即满足三只牛的能找到的草料数量之和等于目标和T，并且满足nums[i] <= nums[j] <= nums[k]。在这里，我们可以考虑使用三重循环来遍历所有可能的组合，并判断是否满足条件。

为了避免重复的牛群组合，我们可以在遍历过程中设置一些条件，比如nums[i] > target / 3时可以直接跳出循环，因为在后续的遍历中，即使后面的牛的草料数量更大，也无法满足nums[i] <= nums[j] <= nums[k]的条件。

思路如下：

首先对数组进行排序，这样可以方便判断nums[i] <= nums[j] <= nums[k]。

使用三重循环遍历所有可能的组合，i从0到n-3，j从i+1到n-2，k从j+1到n-1，其中n为数组长度。

在循环中，对当前的三只牛判断是否满足条件：nums[i] + nums[j] + nums[k] == target，并且 nums[i] <= nums[j] <= nums[k]。

如果满足条件，将这个组合记录下来。

本题解析所用的编程语言:C++

完整且正确的编程代码

class Solution {
public:
    vector<vector<int>> findThreeCows(vector<int>& nums, int target) {
        vector<vector<int>> result;
        int n = nums.size();
        if (n < 3) {
            return result;
        }

        // 首先对数组进行排序
        sort(nums.begin(), nums.end());

        for (int i = 0; i < n - 2; ++i) {
            // 如果当前最小的牛的草料数量已经大于目标和的三分之一，后面无论如何都无法满足条件，直接退出循环
            if (nums[i] > target / 3) {
                break;
            }

            // 跳过重复的牛，避免重复组合
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }

            int left = i + 1; // 左指针
            int right = n - 1; // 右指针

            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[i], nums[left], nums[right]});

                    // 跳过重复的牛，避免重复组合
                    while (left < right && nums[left] == nums[left + 1]) {
                        ++left;
                    }
                    while (left < right && nums[right] == nums[right - 1]) {
                        --right;
                    }

                    // 移动指针
                    ++left;
                    --right;
                } else if (sum < target) {
                    // 和小于目标值，左指针右移
                    ++left;
                } else {
                    // 和大于目标值，右指针左移
                    --right;
                }
            }
        }

        return result;
    }
};