leetcode-四数之和

原理和三数之和相同，但多了一层循环，复杂度为 O(n^3)。

#include <vector>
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
vector<vector<int>> fourSum(vector<int> &nums, int target) {
    sort(nums.begin(), nums.end());
    vector<vector<int>> res;
    int size = nums.size();
    for (int i = 0; i < size - 3; i++) {
        // 去除重复
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        for (int j = i + 1; j < size - 2; j++) {
            // 去除重复
            if (j > i + 1 && nums[j] == nums[j - 1]) {
                continue;
            }
            int left = j + 1;
            int right = size - 1;
            while (left < right) {
                if (nums[i] + nums[j] + nums[left] + nums[right]==target) {
                    res.push_back(vector<int>({ nums[i] , nums[j] , 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 (nums[i] + nums[j] + nums[left] + nums[right] > target) {
                    right--;
                }
                else {
                    left++;
                }
            }
        }
    }
    return res;
}
void main() {
    vector<int> vecInt = { -1,-5,-5,-3,2,5,0,4 };
    auto item = fourSum(vecInt, -7);
    for (auto pitem:item) {
        for (auto citem : pitem) {
            cout << citem << '\t';
        }
        cout << endl;
    }
}