Completed
Dec 25, 2024
标签
哈希表
数组
双指针
相关企业
难度
中等
- 题目描述：给定一个数组，找到3个数，使其和为0，要求这三个数不重复。返回所有和为0的三个数的元组
- 代码思路：暴力解法，三层循环时间复杂度太高。使用双指针，首先对数组进行排序，遍历数组，每遍历到第i个的时候，left指针指向i+1，right指向length-1，判断当前三数的和如果大于0，则right—，如果小于0，则left++，如果等于0，则这三个数就是其中一个解
- 在实际解题过程要注意边界条件
- 遍历的i去重：如果当前遍历的i和上一个i-1的数相同大小，则没必要再检查left和right，因为上一层循环无论是否有答案，一定已经检查过一遍，这次如果再遍历一遍则重复
- left的去重，如果当前的（i，left，right）已经是一个解添加到res中，则向右移动left直到left指向的数与当前left不同，避免重复
- right的去重，与left去重一样，如果得到一个解后，将right左移动直到right指向的数与当前right不同
- 整体来看，三数之和使用双指针的方法将时间复杂度由暴力的O(n³)降低为O(n²)
- 更加优化可以加入剪枝操作，详细见下一题，LC18四数之和
