求Leetcode 3Sum 能过大数据的python解法…… - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

求Leetcode 3Sum 能过大数据的python解法……

求Leetcode 3Sum 能过大数据的python解法……# JobHunting - 待字闺中

h*72014-02-18 08:02

1 楼

不光是这道题，还有一些别的题python过不了。不才解法如下，之前写的一个不用查
list的版本也没过。
另外貌似像import sys; min = sys.maxint 这种都编译不过去？
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
n = len(num)
res= []
if n<3:
return res
for i in range(n-2):
k = i + 1
j = n - 1
while k < j:
sum = num[i] + num[j] + num[k]
if sum < 0:
k += 1
elif sum > 0:
j -= 1
else:
comb = [num[i], num[k], num[j]]
if comb not in res:
res.append(comb)
k += 1
j -= 1
return res

m*c2014-02-18 08:02

2 楼

试试skip duplicate element，而不是用comb not in res来判断重复的。

h*72014-02-18 08:02

3 楼

试了也过不了如下：
class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
num.sort()
n = len(num)
res= []
if n<3:
return res
for i in range(n-2):
j = n-1
if i > 0 and num[i] == num[i-1]:
continue
k = i + 1
while k < j:
sum = num[i] + num[j] + num[k]
if sum < 0:
k += 1
elif sum > 0:
j -= 1
else:
res.append([num[i], num[k], num[j]])
k += 1
j -= 1
while k < j and num[k+1] == num[k]:
k += 1
while k < j and num[j-1] == num[j]:
j -= 1
return res

【在 m********c 的大作中提到】

: 试试skip duplicate element，而不是用comb not in res来判断重复的。

J*e2014-02-18 08:02

4 楼

sum >0, sum <0 后面也要去重复。

【在 h*****7 的大作中提到】

: 试了也过不了如下：
: class Solution:
: # @return a list of lists of length 3, [[val1,val2,val3]]
: def threeSum(self, num):
: num.sort()
: n = len(num)
: res= []
: if n<3:
: return res
: for i in range(n-2):

c*p2014-02-18 08:02

5 楼

can leetcode use python now?!!

k*32014-02-18 08:02

6 楼

class Solution:
# @return a list of lists of length 3, [[val1,val2,val3]]
def threeSum(self, num):
if len(num) < 3:
return []
num.sort()
final_results = []
for i in range(len(num)-2):
if i == 0 or num[i] > num[i-1]:
first = num[i]
sum_of_two = 0 - first
left_index = i + 1
right_index = len(num) - 1
while left_index < right_index:
tmp_sum = num[left_index] + num[right_index]
result = []
if tmp_sum == sum_of_two:
result.append(num[i])
result.append(num[left_index])
result.append(num[right_index])
final_results.append(result)
left_index += 1
right_index -= 1
while right_index > left_index and num[right_index]
== num[right_index+1]:
right_index -= 1
while left_index < right_index and num[left_index] =
= num[left_index-1]:
left_index += 1
elif tmp_sum < sum_of_two:
left_index += 1
else:
right_index -= 1
return final_results

【在 h*****7 的大作中提到】

: 不光是这道题，还有一些别的题python过不了。不才解法如下，之前写的一个不用查
: list的版本也没过。
: 另外貌似像import sys; min = sys.maxint 这种都编译不过去？
: class Solution:
: # @return a list of lists of length 3, [[val1,val2,val3]]
: def threeSum(self, num):
: num.sort()
: n = len(num)
: res= []
: if n<3: