美文网首页
八. Array 2 3Sum

八. Array 2 3Sum

作者: 何大炮 | 来源:发表于2018-03-20 10:43 被阅读0次

Idea:
Normally, I need 3 for loops to traversal. However, there must be a increasing order in the (i, m, j), for example i <= m <= j. Then x could start from the minimum and m starts from maximum, meanwhile, y is a random value.
considering i + m + j = 0, it can be changed into j+i = -m, which means i , as a smaller value, + j, as a larger value, is equal -m.
Known as Sandwich Theorem, i +=1 and j -=1. In one loop, we can go through all the possibilities of m.

class Solution:
    """
    @param numbers: Give an array numbers of n integer
    @return: Find all unique triplets in the array which gives the sum of zero.
    """
    def threeSum(self, numbers):
        # write your code here
        list = []
        numbers.sort()
        
        for m in range(0, len(numbers)):
            j = len(numbers)-1
            i = 0
            while j != i:
                if i == m:
                    i +=1
                    continue
                if j == m:
                    j -=1
                    continue
                
                if numbers[i] + numbers[j] + numbers[m] == 0:
                    three = [numbers[i], numbers[j], numbers[m]]
                    three.sort()
                   # exclude the duplicate 
                    if list.count(three)  == 0:
                        list.append(three)
                        
                if numbers[i] + numbers[j]  + numbers[m] > 0:
                    j -=1     
                else:
                    i +=1                            
        return list

相关文章

网友评论

      本文标题:八. Array 2 3Sum

      本文链接:https://www.haomeiwen.com/subject/tvevqftx.html