一道算法题-三数之和
最新回答
七喵
2026-07-17 23:51:16
三数之和是一道经典的算法题，要求找出数组中所有不重复的三元组，使得它们的和为0。以下是针对该问题的详细解答：
解题思路排序数组：首先对数组进行排序，这样可以方便地跳过重复的元素，并且可以利用双指针技术来优化查找过程。
遍历数组：使用一个外层循环遍历数组中的每一个元素，作为三元组的第一个元素。对于每一个元素，使用双指针技术在剩余的数组部分中寻找另外两个元素，使得它们的和等于当前元素的相反数（即三数之和为0）。
双指针查找：对于当前元素nums[i]，初始化两个指针left和right，分别指向i+1和数组的末尾。计算nums[i] + nums[left] + nums[right]的和：
如果和为0，则找到一个有效的三元组。
如果和小于0，则移动left指针向右，以增加和。
如果和大于0，则移动right指针向左，以减少和。
跳过重复元素：在遍历和双指针移动的过程中，跳过重复的元素以避免重复的三元组。
以下是基于上述思路的Go语言实现：
import "sort"func threeSum(nums []int) [][]int { var result [][]int sort.Ints(nums) n := len(nums) for i := 0; i < n-2; i++ { if i > 0 && nums[i] == nums[i-1] { continue // 跳过重复元素 } left, right := i+1, n-1 for left < right { sum := nums[i] + nums[left] + nums[right] if sum == 0 { result = append(result, []int{nums[i], nums[left], nums[right]}) // 跳过重复元素 for left < right && nums[left] == nums[left+1] { left++ } for left < right && nums[right] == nums[right-1] { right-- } left++ right-- } else if sum < 0 { left++ } else { right-- } } } return result}代码解释排序：使用sort.Ints(nums)对数组进行排序，以便后续的双指针操作。
外层循环：遍历数组中的每一个元素nums[i]，作为三元组的第一个元素。如果当前元素与前一个元素相同，则跳过以避免重复。
双指针查找：
初始化left和right指针，分别指向i+1和数组末尾。
计算三数之和sum：
如果sum == 0，记录三元组，并移动left和right指针跳过重复元素。
如果sum < 0，移动left指针向右以增加和。
如果sum > 0，移动right指针向左以减少和。
返回结果：将找到的所有不重复的三元组返回。
- 时间复杂度：排序的时间复杂度为O(n log n)，外层循环和双指针查找的时间复杂度为O(n^2)，因此总的时间复杂度为O(n^2)。
- 空间复杂度：除了存储结果的数组外，只使用了常数级别的额外空间，因此空间复杂度为O(1)（不考虑存储结果的空间）。
这种方法通过排序和双指针技术高效地解决了问题，同时避免了重复的三元组，是一种经典的解决方案。
热门标签
