leetcode

leetcode 刷题心得与题解

15. 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]
]

O（n3）的时间复杂度经过修改也没啥用

固定i，j、k为双向指针，j从头开始，k从尾开始遍历。
当和小于0时，j减1，当和大于0时，k加1
当找到一个值时，不能当做此时i的固定结果，因为可能有多个，所以需要再把j、k其中之一改变，j加1或者k减1都可以

class Solution(object):
    def threeSum(self, nums):
        length = len(nums)
        resultList = []
        nums.sort()
        for i in range(0,length-2):
            j = i + 1
            k = length - 1
            while (j < k):
                sum0 = nums[i] + nums[j] + nums[k]
                if (sum0 == 0):
                    result = []
                    result.append(nums[i])
                    result.append(nums[j])
                    result.append(nums[k])
                    if result not in resultList:
                        resultList.append(result)
                    j +=1
                if (sum0 < 0):
                    j +=1
                if (sum0 > 0):
                    k -=1
        return resultList