【刷题记录】18. 四数之和
一、题目描述
来源:力扣(LeetCode)
给你一个由 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:
复制代码
示例 2:
复制代码
提示:
1 <= nums.length <= 200
-109 <= nums[i] <= 109
-109 <= target <= 109
二丶思路分析
排序 + 双指针
这个题目 和 【刷题记录】15.三数之和 的思路是一样的,只不过是从三个数,变成了四个数字的处理。
定义 四个 指针
i
,j
,L
,R
在确定两个数
i
,j
的情况下,双指针L
,R
从两边遍历,查找。
三、代码实现
复制代码
复杂度分析
时间复杂度:,其中 n
是数组的长度。排序的时间复杂度是 ,枚举四元组的时间复杂度是 ,因此总时间复杂度为
空间复杂度:,按照题目中 就是存储排序后的数组所占用。
运行结果
总结
这个题目是个以前做过题目的一个变形,从三元变成了四元,但是处理的思路是一样。只是处理的步骤会多一下。
所以这种题目,只要理解一个,一类的问题都能迎刃而解。继续加油~
版权声明: 本文为 InfoQ 作者【WangNing】的原创文章。
原文链接:【http://xie.infoq.cn/article/facb270fcc3b31bf5e63cf43f】。
本文遵守【CC-BY 4.0】协议,转载请保留原文出处及本版权声明。
评论