leetcode——18.4sum题解

 题目要求：

18.4sum

    给出一个整型数组，寻找其中所有不同的子数组（a，b，c，d）使得a，b，c，d的和等于一个给定的数target

    代码：

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> result;
        if (nums.size() < 4)
            return result; // If there are less than 4 elements, return empty result
        sort(nums.begin(), nums.end());
        int n = nums.size();
        for (int i = 0; i < n - 3; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) // Skip duplicate elements
                continue;
            for (int j = i + 1; j < n - 2; ++j) {
                if (j > i + 1 && nums[j] == nums[j - 1]) // Skip duplicate elements
                    continue;
                int left = j + 1;
                int right = n - 1;
                while (left < right) {
                    long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right]; // Convert to long long to avoid overflow
                    if (sum == target) {
                        result.push_back({nums[i], nums[j], nums[left], nums[right]});
                        while (left < right && nums[left] == nums[left + 1]) // Skip duplicate elements
                            left++;
                        while (left < right && nums[right] == nums[right - 1]) // Skip duplicate elements
                            right--;
                        left++;
                        right--;
                    } else if (sum < target) {
                        left++;
                    } else {
                        right--;
                    }
                }
            }
        }
        return result;
    }
};

      
	
	
	

前提

    1.要有nums.size（）>=4

    2.target可以提供nums中的元素相加得到（要考虑没有结果的情况，本题中给出的数据是一定有结果的）

    3.数据大小的判定：比如这里的nums就是一个long long型变量而不是普通的int型（int型无法通过编译）

逻辑

    对撞指针，索引为left和right。

    

    索引i和索引j是两个无条件的循环，所需的时间复杂度是O(N^2)在j循环后又有一个对撞指针其时间复杂度是O（N）所以总共的时间复杂度为O（N^3）。

    时间复杂度有点高，为了降低时间复杂度，可以使用空间换时间（比如将nums[i]+nums[j]合成一个数据，开辟一个nums.size（）*nums.size（）的数组存放这些数据可以将时间复杂度将为O（N^2）现在的空间复杂度为：O(N^2)。）

    空间换时间是一种具体的方法。在很多情况下，时间比空间更重要。