2023-7-15每日一题

一、题目编号

18. 四数之和

二、题目链接

点击跳转到题目位置

三、题目描述

给你一个由 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.length <= 200
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹

四、解题代码

class Solution {
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {vector<vector<int>> res;int n = nums.size();if(n < 4){return res;}sort(nums.begin(), nums.end());for(int i = 0; i < n; ++i){while(i != 0 && i < n && nums[i] == nums[i-1]){++i;}for(int j = i + 1; j < n; ++j){while(j != i + 1 && j < n && nums[j] == nums[j - 1]){++j;}int left = j + 1;int right = n - 1;while(left < right){long long temp = (long long)nums[left] + nums[right] + nums[i] + nums[j];if(temp < target){++left;} else if(temp == target){res.push_back({nums[i], nums[j], nums[left], nums[right]});++left;--right;while(left <= right && nums[left] == nums[left - 1]){++left;}while(left <= right && nums[right] == nums[right + 1]){--right;}} else{--right;}}}}return res;}
};

五、解题思路

(1) 本道题目是三数之和的进阶版，与三数之和差别不大，如果对于三数之和还不了解的可以阅读该篇文章——2023-07-08 LeetCode每日一题（三数之和）

(2) 还是一样的思考方式，我们的题目要求的是寻找到四个数字，不重不漏的等于target。那么我们先对原始数组进行排序，这样更有利于我们进行不重不漏。

(3) 我们如果采用四层循环+哈希判断方式，时间复杂度很高，一定是无法通过题目的。所以我们要另择良木而栖。我们设置最外层循环遍历第一个数字，要使得结果中第一个数字不同，那么如果该数字与前面一个数字相同，那么该数字为该值的所有可能性都已经找出来了，没必要第一个数字还为同样的值，i++。

(4) 这个时候我们将问题转化成三数之和的问题了，只不过所要找的数字之和等于的不是target，等于的是target - nums[i]。因为在三数之和这篇文章中已经写的十分详细了，所以不多赘述。不过大致的思路与(3)中的思路相同，如何不重不漏，然后只剩下两个数字的时候通过双指针的手法减少时间复杂度即可。