做网站的属于什么行业,淘宝网站开发实训报告,黑白灰网站,完美代码的网站文章目录 题目描述算法原理排序双指针 代码实现排序双指针复杂度分析时间复杂度#xff1a;O(N^3^)空间复杂度#xff1a;O(logN)或者O(N) 题目描述
题目链接#xff1a;18.四数之和
算法原理
排序双指针
依次固定⼀个数a #xff1b;在这个数a 的后⾯区间上#x… 文章目录 题目描述算法原理排序双指针 代码实现排序双指针复杂度分析时间复杂度O(N^3^)空间复杂度O(logN)或者O(N) 题目描述
题目链接18.四数之和
算法原理
排序双指针
依次固定⼀个数a 在这个数a 的后⾯区间上利⽤「三数之和」找到三个数使这三个数的和等于target - a 即可。 PS没做过三数之和的同学建议先去做一下三数之和再来做这道题。
代码实现
排序双指针
class Solution {
public:vectorvectorint fourSum(vectorint nums, int target) {int n nums.size();vectorvectorint vv;sort(nums.begin(),nums.end()); //1.排序for(int i 0;i n;)//2.固定一个数{for(int j i 1;j n;)//3.固定三数之和的第一个数{int left j 1,right n - 1;long long sum (long long)target - nums[i] - nums[j];while(left right){long long tmp (long long) nums[left] nums[right];if(tmp sum)right--;else if(tmp sum)left;else{vv.push_back({nums[i],nums[j],nums[left],nums[right]});left;right--;while(left right nums[left] nums[left - 1])left;//去重leftwhile(left right nums[right] nums[right 1])right--;//去重right}}j;while(j n nums[j] nums[j - 1])j;//去重j}i;while(i n nums[i] nums[i - 1])i;//去重i}return vv;}
};复杂度分析
时间复杂度O(N3)
其中N是数组的长度。排序的时间复杂度是 O(NlogN)枚举四元组的时间复杂度是O(N3)因此总时间复杂度为 O(N3NlogN)O(N3)。
空间复杂度O(logN)或者O(N)
其中N是数组的长度。空间复杂度主要取决于排序额外使用的空间。此外排序修改了输入数组nums实际情况中不一定允许因此也可以看成使用了一个额外的数组存储了数组nums的副本并排序空间复杂度为O(N)。
