Question: http://oj.leetcode.com/problems/3sum/
Question Name: 3Sum
Classic question. For more information, you could read the Wikipedia.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 | class Solution: # @return num[i]list of lists of length 3, [[val1,val2,val3]] def threeSum(self, num): num.sort() result = [] i = 0 # For the first item while i < len(num) - 2: j = i + 1 # For the middle item k = len(num) - 1 # For the last item while j < k: if num[i]+ num[j] + num[j] > 0 or num[i]+ num[k]+ num[k]< 0: # num[k] >= any num[j], num[j] <= any num[k] # Impossible to find a answer in the future break if num[i]+ num[j]+num[k]== 0: # Because the num is sorted, so the num[i] <= num[j] <= num[k] # And in every round, i or j/k is different from the previous # round. Therefore, the answer [num[i], num[j], num[k]] is new # and unique for the result set. result.append([num[i], num[j], num[k]]) # Skip duplicate num[j-1] and num[k+1] j += 1 while j < k+1 and num[j] == num[j-1]: j += 1 k -= 1 while k > j-1 and num[k] == num[k+1]: k -= 1 elif num[i] + num[j]+ num[k]< 0: # Skip duplicate num[j-1] j += 1 while j < k+1 and num[j] == num[j-1]: j += 1 else: # Skip duplicate num[k+1] k -= 1 while k > j-1 and num[k] == num[k+1]: k -= 1 # Skip duplicate num[i-1] i += 1 while i < len(num)-1 and num[i] == num[i-1]: i += 1 return result |
Thanks for the solution, it’s really helpful. This article http://bit.ly/29YmZI4 also has a in-depth analysis of 3sum question with variations.