LeetCode第十八题：四数之和

admin
学习
2024-03-05
51热度
0评论

1.题目描述

给你一个由 n 个整数组成的数组 nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] （若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意顺序 返回答案。

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0

输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

提示：

1 <= nums.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

2.解题思路

解法一：暴力(不通过)

描述：使用四层嵌套循环分别遍历数组中的每个元素，其中第一层循环选定第一个数，第二层循环选定第二个数，第三层循环选定第三个数，第四层循环选定第四个数。
时间复杂度：O(n^4)。其中 n 是数组 nums 的长度。
空间复杂度：O(1)。
参考代码：

java版：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> result = new ArrayList<>();
        // 第一层循环
        for (int i = 0; i < nums.length - 3; i++) {
            // 去重
            if (i > 0 && nums[i] == nums[i - 1])
                continue;

            // 第二层循环
            for (int j = i + 1; j < nums.length - 2; j++) {
                // 去重
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;

                // 第三层循环
                for (int k = j + 1; k < nums.length - 1; k++) {
                    // 去重
                    if (k > j + 1 && nums[k] == nums[k - 1])
                        continue;

                    // 第四层循环
                    for (int l = k + 1; l < nums.length; l++) {
                        // 去重
                        if (l > k + 1 && nums[l] == nums[l - 1])
                            continue;

                        // 检查四元组之和是否等于目标值
                        if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
                            // 添加到结果列表
                            result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
                        }
                    }
                }
            }
        }
        return result;
    }
}

C++版：

class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		sort(nums.begin(), nums.end()); // 先排序，便于去重
		vector<vector<int>> result;

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

			for (int j = i + 1; j < nums.size(); ++j) {
				// 第二重循环去重
				if (j > i + 1 && nums[j] == nums[j - 1]) continue;

				for (int k = j + 1; k < nums.size(); ++k) {
					// 第三重循环去重
					if (k > j + 1 && nums[k] == nums[k - 1]) continue;

					for (int l = k + 1; l < nums.size(); ++l) {
						// 第四重循环去重
						if (l > k + 1 && nums[l] == nums[l - 1]) continue;

						if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
							result.push_back({ nums[i], nums[j], nums[k], nums[l] });
						}
					}
				}
			}
		}

		return result;
	}
};

C版：

 // 辅助函数：用于qsort的比较函数
int compare(const void* a, const void* b) {
	return (*(int*)a - *(int*)b);
}

int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
	int maxSize = 200; // 假设最多有200个结果，实际情况可能需要根据输入动态调整
	int** result = (int**)malloc(maxSize * sizeof(int*));
	*returnColumnSizes = (int*)malloc(maxSize * sizeof(int));
	*returnSize = 0;

	// 对数组进行排序，便于去重和后续处理
	qsort(nums, numsSize, sizeof(int), compare);

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

		for (int j = i + 1; j < numsSize; j++) {
			// 去重
			if (j > i + 1 && nums[j] == nums[j - 1]) continue;

			for (int k = j + 1; k < numsSize; k++) {
				// 去重
				if (k > j + 1 && nums[k] == nums[k - 1]) continue;

				for (int l = k + 1; l < numsSize; l++) {
					// 去重
					if (l > k + 1 && nums[l] == nums[l - 1]) continue;

					if (nums[i] + nums[j] + nums[k] + nums[l] == target) {
						result[*returnSize] = (int*)malloc(4 * sizeof(int));
						(*returnColumnSizes)[*returnSize] = 4;
						result[*returnSize][0] = nums[i];
						result[*returnSize][1] = nums[j];
						result[*returnSize][2] = nums[k];
						result[*returnSize][3] = nums[l];
						(*returnSize)++;
					}
				}
			}
		}
	}

	return result;
}

解法二：排序+双指针

描述：首先对输入数组nums进行排序。排序是为了之后应用双指针策略以及去重。通过两层循环固定前两个数nums[i]和nums[j]。这里需要注意去重，以避免重复计算。在每一对固定数后面的数组中，使用双指针left和right来寻找符合条件的两个数，使得nums[i] + nums[j] + nums[left] + nums[right] == target。根据四数之和与目标值的比较，移动left和right指针。在找到每一组符合条件的四元组后，需要去重，即跳过相邻且相同的数。将符合条件的四元组保存到结果列表中。
时间复杂度：O(n^3)。排序的时间复杂度是O(nlogn)，双层循环时间复杂度为O(n^2)，双指针查找：对于每一对固定的数，双指针部分的时间复杂度为O(n)。所以总体时间复杂度为O(nlogn + n^2 * n) = O(n^3)。
空间复杂度：O(logn)。主要是排序所需的空间，快速排序的空间复杂度平均是O(logn)。
参考代码：

java版：

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        // 对数组进行排序
        Arrays.sort(nums);
        // 存放结果
        List<List<Integer>> res = new ArrayList<>();

        int n = nums.length;
        // 第一层循环，遍历数组，选定第一个数
        for (int i = 0; i < n - 3; i++) {
            // 去重：跳过重复的元素，以避免在结果列表中出现重复的四元组
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            // 第二层循环，选定第二个数
            for (int j = i + 1; j < n - 2; j++) {
                // 去重：同样地，跳过重复的元素
                if (j > i + 1 && nums[j] == nums[j - 1])
                    continue;
                // 初始化双指针
                int left = j + 1;
                int right = n - 1;
                // 使用双指针在当前的子数组中寻找和为target的两个数
                while (left < right) {
                    long sum = (long)nums[i] + nums[j] + nums[left] + nums[right];
                    // 当找到符合条件的四元组时
                    if (sum == target) {
                        // 将其添加到结果列表中
                        res.add(Arrays.asList(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 (sum < target) {
                        // 如果当前四数之和小于目标值，则移动左指针以增加总和
                        left++;
                    } else {
                        // 如果当前四数之和大于目标值，则移动右指针以减少总和
                        right--;
                    }
                }
            }
        }
        // 返回所有找到的符合条件的四元组
        return res;
    }
}

C++版：

class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		// 存放结果
		long long targetLL = static_cast<long long>(target);

		vector<vector<int>> result;
		// 对数组进行排序
		sort(nums.begin(), nums.end());

		int n = nums.size();
		// 第一层循环，遍历数组，选定第一个数
		for (int i = 0; i < n - 2; i++) {
			// 去重：跳过重复的元素，以避免在结果列表中出现重复的四元组
			if (i > 0 && nums[i] == nums[i - 1]) continue;
			// 第二层循环，选定第二个数
			for (int j = i + 1; j < n - 2; j++) {
				// 去重：同样地，跳过重复的元素
				if (j > i + 1 && nums[j] == nums[j - 1]) continue;
				// 初始化双指针
				int left = j + 1, right = n - 1;
				// 使用双指针在当前的子数组中寻找和为target的两个数
				while (left < right) {
					// 使用 long long 类型计算和，避免溢出
					long long sum = static_cast<long long>(nums[i]) + nums[j] + nums[left] + nums[right];
					// 当找到符合条件的四元组时
					if (sum == targetLL) {
						// 将其添加到结果列表中
						result.push_back({ 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 (sum < targetLL) {
						// 如果当前四数之和小于目标值，则移动左指针以增加总和
						left++;
					}
					else {
						// 如果当前四数之和大于目标值，则移动右指针以减少总和
						right--;
					}
				}
			}
		}
		return result;
	}
};

C版：

// 比较函数，用于qsort
int compare(const void *a, const void *b) {
    return (*(int *)a - *(int *)b);
}

// 主函数
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {
    // 先对数组进行排序
    qsort(nums, numsSize, sizeof(int), compare);
    
    // 动态分配结果数组的初始空间
    int **res = (int **)malloc(numsSize * numsSize * sizeof(int *));
    *returnColumnSizes = (int *)malloc(numsSize * numsSize * sizeof(int));
    *returnSize = 0;
    
    // 四重循环来遍历所有可能的四元组
    for (int i = 0; i < numsSize; ++i) {
        // 跳过重复的数字
        if (i > 0 && nums[i] == nums[i - 1]) continue;
        
        for (int j = i + 1; j < numsSize; ++j) {
            // 跳过重复的数字
            if (j > i + 1 && nums[j] == nums[j - 1]) continue;
            
            int left = j + 1;
            int right = numsSize - 1;
            
            while (left < right) {
                long long sum = (long long)nums[i] + nums[j] + nums[left] + nums[right];
                if (sum == target) {
                    // 找到一个解，动态分配空间并保存这个结果
                    res[*returnSize] = (int *)malloc(4 * sizeof(int));
                    res[*returnSize][0] = nums[i];
                    res[*returnSize][1] = nums[j];
                    res[*returnSize][2] = nums[left];
                    res[*returnSize][3] = nums[right];
                    (*returnColumnSizes)[*returnSize] = 4;
                    (*returnSize)++;
                    
                    // 移动指针并跳过重复的数字
                    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 res;
}