leetcode15 -- 3Sum

leetcode15 -- 3Sum

题目

Given an array nums of n integers, are there elements a, b, c in nums 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.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

解答

这个题相比two sum又难了一些,现在是要找到所有的三个数加起来等于0的组和,其实不是0的话也可以,这个题当然暴力肯定可以,但是更高效的办法也有,

比如

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        
        nums.sort()
        
        ret = []
        
        if len(nums) ==0 or nums[0]>0 or nums[-1] <0:
            return []
        
        for k in range(len(nums)):
            if nums[k]>0:
                break
                
            if k>0 and nums[k]==nums[k-1]:
                continue
            
            target = 0-nums[k]
            
            i = k+1
            j = len(nums)-1
            
            while i<j:
                summ = nums[i]+nums[j]
                if summ==target:
                    ret.append([nums[k],nums[i],nums[j]])
                
                    while i<j and nums[i]==nums[i+1]:
                        i+=1
                    while i<j and nums[j]==nums[j-1]:
                        j -= 1
                    
                    i += 1
                    j -= 1
                elif summ<target:
                    i += 1
                else:
                    j -= 1
                    
        return ret 
                
                    

上面的做法是先对数组排一个序,然后遍历每一个元素,并将其相反数作为target用后面的部分来找和为target的两个数。这样的话就快了很多,整个下来排序是O(nlogn), 后面的做法是O(n^2),所以最终是O(n^2).但是要注意,如果遍历到的数是正数的话就不用遍历了,而且如果排完序之后的第一个数大于0或者最后一个数小于0的时候都直接返回结果为空。

此外题目中要求的是不能够有重复的,所以还要做去重处理,这里就是在最外层for的时候,如果前后两个元素一样的话,就直接过去,虽然最终允许有两个-1这种出现,但是作为第一个数,他们不能够相等,同理,作为第二个数他们也不能够相等。

所以在里面加了

 while i<j and nums[i]==nums[i+1]:
                        i+=1
                    while i<j and nums[j]==nums[j-1]:
                        j -= 1



打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦