首页 > 代码库 > leetcode 3sum question

leetcode 3sum question

2024-10-19 10:38:02   213人阅读

摘要：

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

问题分析：
 对数组实现3个值的求和，可以分解为两个数值的和；问题需要考虑到过滤重复的解决方案和考虑到算法复杂度；
 1 class Solution(object):
 2     def threeSum(self, nums):
 3         """
 4         :type nums: List[int]
 5         :rtype: List[List[int]]
 6         """
 7         nums.sort() # 根据python的内置列表排序，实现排序
 8         result = list()            
 9         if len(nums) < 3:
10             return result # 判断，如果输入列表小于3，直接返回空值
11         for i in range(len(nums) - 2): # 只能遍历到len(nums)-2,否则越界
12             if i > 0 and nums[i] == nums[i-1]:
13                 continue
14             left = i + 1
15             right = len(nums) - 1
16             while left < right:
17                 cur_sum = nums[left] + nums[right]
18                 target_sum = 0 - nums[i]
19                 if cur_sum == target_sum:
20                     temp = [nums[i],nums[left],nums[right]]
21                     result.append(temp)
22                     left +=1 
23                     right -= 1
24                     while left < right and nums[left]==nums[left-1]:
25                         left +=1 
26                     while left < right and nums[right] == nums[right+1]:
27                         right -= 1
28                 elif cur_sum < target_sum:
29                     left += 1
30                 else:
31                     right -= 1
32            return result

代码解析：

　　第一想法：对数组按照i,j,k三个指针指向进行遍历，时间复杂度为O(n3),当数组长度很大时，运算速度过慢，造成无法运算

　　第二想法：通过搜索查看别人答案，上面的代码实现时间复杂度为O(nlogn);逻辑为，遍历一次数组，不重复遍历。转化为求2sum的问题 



leetcode 3sum question


联系
我们