這道題在春節(jié)假期期間做的，實(shí)在沒(méi)有心思做，自己只會(huì)暴力算法，也就是三層嵌套循環(huán)的O(n^3)的算法。
網(wǎng)上有此類問(wèn)題的統(tǒng)一算法，k sum，假期也只了解了3Sum的解法，核心思想是先排序，后使用兩個(gè)指針（其實(shí)就是左右索引）將復(fù)雜度降到了O(n^2)
算法：
排序，O(nlogn)如果是2Sum，那么只需要兩個(gè)指針(lo, hi)，一個(gè)從左一個(gè)從右，向中間搜索。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外加上了一層循環(huán)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新聞熱點(diǎn)
疑難解答
圖片精選
網(wǎng)友關(guān)注
