获取三数之和
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组的数量。
注意:答案中不可以包含重复的三元组(例如[a,b,c]与[c,b,a]为重复),如果无符合要求的三元组,则返回0。
提示:
-
3 <= nums.length <= 3000
-
-10^5 <= nums[i] <= 10^5
-
运行有时间、内存限制
输入格式:
一个整数数组,每个元素其间以“空格”分隔
输出格式:
所有符合题目要求三元组的数量,如果无符合要求的三元组,则返回0。
输入样例1:
在这里给出一组输入。例如:
-1 0 1 2 -1 -4
输出样例1:
在这里给出相应的输出。例如:
2
要解决这个问题,我们可以使用双指针法来寻找所有满足条件的三元组。具体步骤如下:1. 首先对数组进行排序,这样可以方便地使用双指针法。
2. 遍历数组,对于每个元素,使用双指针在剩余的部分寻找两个数,使得这三个数的和为零。
3. 为了避免重复的三元组,我们需要跳过重复的元素。以下是 Python 代码实现:```python
def three_sum(nums):nums.sort() # 对数组进行排序n = len(nums)result = set() # 使用集合来存储结果,避免重复for i in range(n):if i > 0 and nums[i] == nums[i - 1]:continue # 跳过重复的元素left, right = i + 1, n - 1while left < right:total = nums[i] + nums[left] + nums[right]if total == 0:result.add((nums[i], nums[left], nums[right]))left += 1right -= 1# 跳过重复的元素while left < right and nums[left] == nums[left - 1]:left += 1while left < right and nums[right] == nums[right + 1]:right -= 1elif total < 0:left += 1else:right -= 1return len(result)# 读取输入
input_str = input().strip()
nums = list(map(int, input_str.split()))# 计算并输出结果
print(three_sum(nums))
```### 代码解释1. **排序**:首先对输入的数组进行排序,这样可以方便地使用双指针法。
2. **遍历数组**:使用一个 `for` 循环遍历数组中的每个元素,作为三元组中的第一个元素。
3. **双指针法**:对于每个元素,使用双指针在剩余的部分寻找两个数,使得这三个数的和为零。双指针分别从当前元素的下一个位置和数组的末尾开始,向中间移动。
4. **避免重复**:在遍历和移动指针的过程中,跳过重复的元素,以避免重复的三元组。
5. **结果存储**:使用集合来存储结果三元组,集合会自动去重。
6. **返回结果**:返回集合的大小,即不重复的三元组的数量。### 输入输出示例- 输入样例1: `-1 0 1 2 -1 -4`- 输出样例1: `2`
- 输入样例2: `0 1 1`- 输出样例2: `0`这个方法的时间复杂度为 \(O(n^2)\),空间复杂度为 \(O(n)\),在给定的输入限制下是可以接受的。