一倔约、題目
3Sum
二啥刻、解題
使用三重循環(huán)遍歷進行判斷奸鸯，得出的結(jié)果使用sort進行排序，判斷是否在列表之內(nèi)再添加郑什。
三府喳、嘗試與結(jié)果
1）首次嘗試
class Solution(object):
def threeSum(self, nums):
length = len(nums)
resultList = []
for i in range(0,length):
for j in range(i+1,length):
for k in range(j+1,length):
tSum = nums[i] + nums[j] + nums[k]
if tSum == 0:
result = []
result.append(nums[i])
result.append(nums[j])
result.append(nums[k])
result.sort()
if result not in resultList:
resultList.append(result)
return resultList
結(jié)果：TL
2）再次嘗試，先進行sort排序蘑拯，在三重循環(huán)中加入break判斷，當大于0時就跳出兜粘。
class Solution(object):
def threeSum(self, nums):
length = len(nums)
resultList = []
nums.sort()
for i in range(0,length-2):
if nums[i] > 0:
break
for j in range(i+1,length-1):
if nums[i] + nums[j] > 0:
break
for k in range(j+1,length):
if nums[i] + nums[j] + nums[k] == 0:
result = []
result.append(nums[i])
result.append(nums[j])
result.append(nums[k])
if result not in resultList:
resultList.append(result)
if nums[i] + nums[j] + nums[k] > 0:
break
return resultList
結(jié)果：TL
3）O（n3）的時間復(fù)雜度經(jīng)過修改也沒啥用申窘，改成：
- 固定i，j孔轴、k為雙向指針剃法，j從頭開始，k從尾開始遍歷路鹰。
- 當和小于0時贷洲，j減1，當和大于0時晋柱，k加1
- 當找到一個值時优构，不能當做此時i的固定結(jié)果，因為可能有多個雁竞，所以需要再把j钦椭、k其中之一改變，j加1或者k減1都可以
class Solution(object):
def threeSum(self, nums):
length = len(nums)
resultList = []
nums.sort()
for i in range(0,length-2):
j = i + 1
k = length - 1
while (j < k):
sum0 = nums[i] + nums[j] + nums[k]
if (sum0 == 0):
result = []
result.append(nums[i])
result.append(nums[j])
result.append(nums[k])
if result not in resultList:
resultList.append(result)
j +=1
if (sum0 < 0):
j +=1
if (sum0 > 0):
k -=1
return resultList
結(jié)果：AC
