leetcode15：三数之和

题目链接

leetcode

题目描述

给一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。
请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]" <<endl;
}

void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (const vector<int>& num : nums) {
        cout << "[";
        for (const int& num2 : num) {
            cout << num2 << ",";
        }
        cout << "], ";
    }
    cout << "]" <<endl;
}

/*
    两重枚举，无重复构造

    时间复杂度：O(n^2)
        其中 n 是数组的长度。
    空间复杂度：O(n^2)
        结果数组的大小为 n^2。
*/
class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> res;
        sort(nums.begin(), nums.end());

        for (int i = 0; i < nums.size(); i++) {
            if (i > 0 && nums[i] == nums[i-1]) {
                continue; // 去重
            }

            int j = i+1, k = nums.size()-1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.push_back({nums[i], nums[j], nums[k]});
                    while (j < k && nums[j] == nums[j+1]) {
                        j++; // 去重
                    }
                    while (j < k && nums[k] == nums[k-1]) {
                        k--; // 去重
                    }
                    j++, k--;
                } else if (sum < 0) {
                    j++;
                } else if (sum > 0) {
                    k--;
                }
            }
        }

        return res;
    }
};

// 辅助函数：打印数组
void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]" << endl;
}

int main() {
    Solution solution;
    vector<vector<int>> nums_cases = {
        {-1,0,1,2,-1,-4},
        {0,1,1},
        {0,0,0}
    };

    for (auto& nums : nums_cases) {
        vector<vector<int>> result = solution.threeSum(nums);

        cout << "Input: ";
        printArray(nums);
        cout << "Output: ";
        printArray(result);
    }
    
    return 0;
}