Completed
Dec 25, 2024
标签
哈希表
数组
双指针
相关企业
难度
中等
- 题目描述：与三数之和类似，本题是四个数，目标不是0而是target，一定要先做完LC15的三数之和再来看四数之和
- 代码思路：与三数之和思路相同，额外多嵌套一层循环，再在其中用双指针，将复杂度由O(n4)降低至O(n3)
- 剪枝1：当i这个数大于目标了，而且i这个数大于等于0，说明以后都是正数，再怎么相加，都会超过target，则直接break
- 剪枝2：当（i+j）大于target且（i+j）已经大于0了，直接break
- 去重与三数之和一样，分别对i的去重，j的去重，left的去重和right的去重
