如果你想给家添个电视，你的预算会是多少？一千？三千？还是五千？

我闲来无事，就随手在某个购物软件上搜了一下「电视机」，就连最廉价的货色也得千元起步。

但真的有人会买那些太便宜的电视吗？难道他们不担心质量问题，连牌子没人听说过，怎么都感觉不靠谱吧？但是就是这些便宜货，动不动就是10万+的销量。

按现在的消费观来看，200块钱，可能就是十杯奶茶的价钱，甚至连一顿好的都吃不上。但这么点钱，竟然能买到一台电视。

翻了翻卖家的图片，200块的电视长这样。

那么谁会花200块买这种电视？于是我一翻买家秀，竟一时泪目~

买家晒出的照片里，这台200块的电视，有的挂在斑驳的墙上，有的放在乱糟糟的桌子上，旁边是堆满了各种杂物的柜子，有的墙上还挂着孩子的奖状。一看就知道，这些家庭，生活并不宽裕。

在网上看惯了那些高大上的生活方式，我感觉是我飘了，一开始我竟觉得为什么会有人买200块的电视。但实际上，住在出租屋，自己下厨省钱，才是我们的日常。

我们都是普通人，过着普普通通的生活，这就是真相。

下面是今日算法题

今日算法题，来自LeetCode的第18题：四数之和，下面是我的算法思路及实现，让我们来看看吧。

# 算法题目

给定一个包含 n 个整数的数组 nums 和一个目标值 target，找出 nums 中的所有唯一四元组，这四元组的和为 target。每个四元组中的元素必须是不同的。

# 算法思路

1. 排序：首先对数组进行排序，这是使用双指针技术的前提。

   
   

2. 遍历：使用两层循环遍历数组，分别确定前两个数。对于数组中的每对数，使用双指针在剩余部分寻找两个数，使得这四个数的和等于 target。

   
   

3. 双指针：在确定了前两个数后，对数组的剩余部分使用头尾双指针，寻找满足条件的两个数。如果找到了，将它们加入到结果列表中。

   
   

4. 去重：在遍历和双指针搜索过程中，需要跳过重复的元素，以确保结果的唯一性。

# 代码实现

C语言实现

#include<stdio.h>#include<stdlib.h>// 比较函数，用于 qsortintcompare(constvoid *a, constvoid *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(sizeof(int *) * 500); // 假设最多有500组解 *returnColumnSizes = (int *)malloc(sizeof(int) * 500); *returnSize = 0;for (int i = 0; i < numsSize - 3; i++) { // 第一个数if (i > 0 && nums[i] == nums[i-1]) continue; // 去重for (int j = i + 1; j < numsSize - 2; j++) { // 第二个数if (j > i + 1 && nums[j] == nums[j-1]) continue; // 去重int left = j + 1, right = numsSize - 1;while (left < right) { // 双指针查找int sum = nums[i] + nums[j] + nums[left] + nums[right];if (sum == target) { res[*returnSize] = (int *)malloc(sizeof(int) * 4); 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--; } elseif (sum < target) { left++; } else { right--; } } } }return res;} ‍

Java实现

import java.util.ArrayList;import java.util.Arrays;import java.util.List;public classSolution{publicList<List<Integer>> fourSum(int[] nums, int target) {Arrays.sort(nums);List<List<Integer>> res = 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; // 去重 int left = j + 1, right = nums.length - 1;while (left < right) { int sum = 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--; } elseif (sum < target) {left++; } else {right--; } } } }return res; }}

Python实现

def four_sum(nums, target): nums.sort() res = []for i in range(len(nums) - 3):if i > 0 and nums[i] == nums[i-1]:continuefor j in range(i + 1, len(nums) - 2):if j > i + 1 and nums[j] == nums[j-1]:continueleft, right = j + 1, len(nums) - 1whileleft < right: sum = nums[i] + nums[j] + nums[left] + nums[right]if sum == target: res.append([nums[i], nums[j], nums[left], nums[right]])whileleft < right and nums[left] == nums[left+1]:left += 1whileleft < right and nums[right] == nums[right-1]:right -= 1left += 1right -= 1 elif sum < target:left += 1else:right -= 1return res ‍

# 算法解析

这个问题的解法主要依赖于排序和双指针技术。通过排序，我们可以有效地避免重复解，并且可以使用双指针技术来降低时间复杂度。整体算法的时间复杂度为O(n3)，其中 n 是数组的长度。

# 示例和测试

以输入数组 nums = [1, 0, -1, 0, -2, 2] 和目标值 target = 0 为例：

nums = [1, 0, -1, 0, -2, 2]target = 0print(four_sum(nums, target))

输出：

[[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

# 总结

四数之和问题是一个经典的数组和双指针问题，通过排序和双指针技术可以高效地找到所有唯一的四元组。这个方法不仅适用于四数之和问题，也可以扩展到三数之和等类似问题。

热门推荐