[LeetCode]15.3Sum

这道题在春节假期期间做的，实在没有心思做，自己只会暴力算法，也就是三层嵌套循环的O(n^3)的算法。

网上有此类问题的统一算法，k sum，假期也只了解了3Sum的解法，核心思想是先排序，后使用两个指针（其实就是左右索引）将复杂度降到了O(n^2)

算法：

while lo < hi:    if sums[lo] + sums[hi] == target:        result.append([sums[lo], sums[hi]])        lo += 1        hi -= 1        while sums[lo] == sums[lo - 1]:            lo += 1        while sums[hi] == sums[hi + 1]:            hi -= 1    elif sums[lo] + sums[hi] < target:        lo += 1    else:        hi -= 1
3Sum是在2Sum外加上了一层循环
class Solution(object):    def threeSum(self, nums):        """        :type nums: List[int]        :rtype: List[List[int]]        """        # nums = list(set(nums))        # PRint nums        length = len(nums)        result = []        if nums == None or length < 3:            return result        nums.sort()        for x in xrange(0, length - 2):            if nums[x] > 0:                break            else:                if x == 0 or nums[x] > nums[x - 1]:                    left = x + 1                    right = length - 1                    while left < right:                        if nums[x] + nums[left] + nums[right] == 0:                            if [nums[x], nums[left], nums[right]] not in result:                                result.append(                                    [nums[x], nums[left], nums[right]])                            left += 1                            right -= 1                            while left < right and nums[left] == nums[left - 1]:                                left += 1                            while left < right and nums[right] == nums[right + 1]:                                right -= 1                        elif nums[x] + nums[left] + nums[right] < 0:                            left += 1                        else:                            right -= 1        return result