当前位置:实例文章 » JAVA Web实例» [文章]【力扣算法14】之 15. 三数之和 python

【力扣算法14】之 15. 三数之和 python

发布人:shili8 发布时间:2025-01-17 03:32 阅读次数:0

**力扣算法14之三数之和**

### 题目描述给定一个大小为 `n` 的整数数组 `nums`,找到三个和最大的元素。返回此类和的最大值。

### 示例1:

* 输入:`nums = [1,2,3,4,5]`
* 输出:`23`

### 示例2:

* 输入:`nums = [-1,-2,-3,-4,-5]`
* 输出:`-6`

### 示例3:

* 输入:`nums = [0,0,0,0,0]`
* 输出:`0`

### 解决方案#### 方法一:排序后三指针法我们可以先对数组进行升序或降序排序,然后使用三个指针分别指向最小、最大和中间的元素。每次移动指针时,比较当前三个数字之和与之前记录的最大值,并更新最大值。

class Solution:
 def threeSum(self, nums: List[int]) -> int:
 # 对数组进行升序排序 nums.sort()
 max_sum = float('-inf') # 初始化最大值为负无穷 for i in range(len(nums) -2):
 # 如果当前元素与前一个元素相同,跳过此次循环以避免重复计算 if i >0 and nums[i] == nums[i-1]:
 continue left, right = i +1, len(nums) -1 # 初始化左右指针 while left < right:
 current_sum = nums[i] + nums[left] + nums[right]
 # 如果当前和大于最大值,更新最大值 if current_sum > max_sum:
 max_sum = current_sum # 如果当前和小于零,移动右指针以增加和 if current_sum < 0:
 left +=1 else: # 如果当前和大于或等于零,移动左指针以减少和 right -=1 return max_sum


#### 方法二:哈希表法我们可以使用哈希表来存储数字及其出现的次数,然后遍历数组并检查是否存在两个元素之和为目标值的对。时间复杂度为 O(n^2),空间复杂度为 O(n)。

class Solution:
 def threeSum(self, nums: List[int]) -> int:
 max_sum = float('-inf') # 初始化最大值为负无穷 count_dict = {} # 使用哈希表存储数字及其出现的次数 for num in nums:
 if num not in count_dict:
 count_dict[num] =1 else:
 count_dict[num] +=1 for i in range(len(nums) -2):
 for j in range(i +1, len(nums) -1):
 target = -(nums[i] + nums[j]) # 计算目标值 if target in count_dict and count_dict[target] >0:
 current_sum = nums[i] + nums[j] + target # 如果当前和大于最大值,更新最大值 if current_sum > max_sum:
 max_sum = current_sum return max_sum


#### 方法三:双指针法我们可以使用两个指针分别指向数组的两端,然后移动指针以找到三个数字之和为零的组合。时间复杂度为 O(n^2),空间复杂度为 O(1)。

class Solution:
 def threeSum(self, nums: List[int]) -> int:
 max_sum = float('-inf') # 初始化最大值为负无穷 nums.sort() # 对数组进行升序排序 for i in range(len(nums) -2):
 left, right = i +1, len(nums) -1 while left < right:
 current_sum = nums[i] + nums[left] + nums[right]
 # 如果当前和大于最大值,更新最大值 if current_sum > max_sum:
 max_sum = current_sum # 如果当前和小于零,移动右指针以增加和 if current_sum < 0:
 left +=1 else: # 如果当前和大于或等于零,移动左指针以减少和 right -=1 return max_sum


### 总结以上是力扣算法14之三数之和的解决方案。我们使用了三个方法:排序后三指针法、哈希表法和双指针法。每个方法都有其优缺点,选择哪种方法取决于具体问题的需求。

其他信息

其他资源

Top