这道题在春节假期期间做的，实在没有心思做，自己只会暴力算法，也就是三层嵌套循环的O(n^3)的算法。
网上有此类问题的统一算法，k sum，假期也只了解了3Sum的解法，核心思想是先排序，后使用两个指针（其实就是左右索引）将复杂度降到了O(n^2)
算法：
排序，O(nlogn)如果是2Sum，那么只需要两个指针(lo, hi)，一个从左一个从右，向中间搜索。while lo < hi:if sums[lo] + sums[hi] == target:result.append([sums[lo], sums[hi]])lo += 1hi -= 1while sums[lo] == sums[lo - 1]:lo += 1while sums[hi] == sums[hi + 1]:hi -= 1elif sums[lo] + sums[hi] < target:lo += 1else:hi -= 13Sum是在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新闻热点
疑难解答
