Leetcode18——4Sum

文章作者:Tyan
博客:noahsnail.com  |  CSDN  |  简书

1. Description

4Sum

2. Solutions

  • Brute Force

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    class Solution {
    public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    int length = nums.size();
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    for(int i = 0; i < length - 3; i++) {
    if(i != 0 && nums[i] == nums[i - 1]) {
    continue;
    }
    for(int j = i + 1; j < length - 2; j++) {
    if(nums[j] == nums[j - 1] && j != i + 1) {
    continue;
    }
    for(int k = j + 1; k < length - 1; k++) {
    if(nums[k] == nums[k - 1] && k != j + 1) {
    continue;
    }
    for(int l = k + 1; l < length; l++) {
    if(nums[l] == nums[l - 1] && l != k + 1) {
    continue;
    }
    int sum = nums[i] + nums[j] + nums[k] + nums[l];
    if(sum == target) {
    vector<int> temp;
    temp.push_back(nums[i]);
    temp.push_back(nums[j]);
    temp.push_back(nums[k]);
    temp.push_back(nums[l]);
    result.push_back(temp);
    }
    }
    }
    }
    }
    return result;
    }
    };
  • sort and O(n^3)

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    class Solution {
    public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
    int length = nums.size();
    vector<vector<int>> result;
    sort(nums.begin(), nums.end());
    int sum = 0;
    int newTarget = 0;
    int left = 0;
    int right = 0;
    for(int i = 0; i < length - 3; i++) {
    if(i != 0 && nums[i] == nums[i - 1]) {
    continue;
    }
    for(int j = i + 1; j < length - 2; j++) {
    if(nums[j] == nums[j - 1] && j != i + 1) {
    continue;
    }
    newTarget = target - nums[i] - nums[j];
    left = j + 1;
    right = length - 1;
    while(left < right) {
    if(left != j + 1 && nums[left] == nums[left - 1]) {
    left++;
    continue;
    }
    if(right < length - 2 && nums[right] == nums[right + 1]) {
    right--;
    continue;
    }
    sum = nums[left] + nums[right];
    if(sum == newTarget) {
    vector<int> temp;
    temp.push_back(nums[i]);
    temp.push_back(nums[j]);
    temp.push_back(nums[left]);
    temp.push_back(nums[right]);
    result.push_back(temp);
    left++;
    right--;
    }
    else if(sum < newTarget) {
    left++;
    }
    else {
    right--;
    }
    }
    }
    }
    return result;
    }
    };

Reference

  1. https://leetcode.com/problems/4sum/description/
如果有收获,可以请我喝杯咖啡!