3Sum – Leetcode Challenge – Python Solution
This is the python solution for the Leetcode problem – 3Sum – Leetcode Challenge – Python Solution.
Source – qiyuangong’s repository.
class Solution(object): # def threeSum(self, nums): # # skip duplicate # # O(n^3) # if len(nums) < 3: # return [] # nums.sort() # ls = len(nums) # result = [] # for i in range(0, ls - 2): # if nums[i] > 0: # break # if i > 0 and nums[i] == nums[i - 1]: # continue # j = i + 1 # k = ls - 1 # while(j < k): # temp = [nums[i], nums[j], nums[k]] # s = sum(temp) # jtemp = nums[j] # ktemp = nums[k] # if s <= 0: # j += 1 # while(j < k and jtemp == nums[j]): # j += 1 # if s == 0: # result.append(temp) # else: # k -= 1 # while(j < k and ktemp == nums[k]): # k -= 1 # return result # def threeSum(self, nums): # """ # :type nums: List[int] # :rtype: List[List[int]] # """ # # using multiple 2 sum # nums.sort() # result, visited = set(), {} # for i in xrange(len(nums) - 2): # table, target = {}, -nums[i] # if nums[i] not in visited: # for j in xrange(i + 1, len(nums)): # if nums[j] not in table: # table[target - nums[j]] = j # else: # result.add((nums[i], target - nums[j], nums[j])) # visited[nums[i]] = 1 # return list(result) def threeSum(self, nums): res = [] nums.sort() ls = len(nums) for i in range(ls - 2): if i > 0 and nums[i] == nums[i - 1]: continue j = i + 1 k = ls - 1 while j < k: curr = nums[i] + nums[j] + nums[k] if curr == 0: res.append([nums[i], nums[j], nums[k]]) while j < k and nums[j] == nums[j + 1]: j += 1 while j < k and nums[k] == nums[k - 1]: k -= 1 j += 1 k -= 1 elif curr < 0: j += 1 else: k -= 1 return res