leetcode -18.4Sum
2484 ワード
私の解法は2 Sumと同じアルゴリズムを利用しています.
1.元の配列のソート
2.最初と最後の2つのポインタを設定します.2つの数の和がtargetより大きい場合、テールポインタは左に1ビット移動します.2つの数の和がtargetより小さい場合、テールポインタは右に1ビット移動します.
4 Sumの解法は,4つの数字であるため,2つのループ配列を用いて最初の2つの数字を決定し,残りの2つの数字とtargetは2 Sumのアルゴリズムを用いて完成できる.しかしアルゴリズムの実行時間は長い.
コードは次のとおりです.
discuss領域のpythonの最速コードは次のとおりです.
このコードコアも2 Sumのアルゴリズムを用い,再帰的に任意の数のNSum問題を解くことができる.しかし速度は120 msと速く、問題は重複数の判断を何度も少なくしたことだ.
1.元の配列のソート
2.最初と最後の2つのポインタを設定します.2つの数の和がtargetより大きい場合、テールポインタは左に1ビット移動します.2つの数の和がtargetより小さい場合、テールポインタは右に1ビット移動します.
4 Sumの解法は,4つの数字であるため,2つのループ配列を用いて最初の2つの数字を決定し,残りの2つの数字とtargetは2 Sumのアルゴリズムを用いて完成できる.しかしアルゴリズムの実行時間は長い.
コードは次のとおりです.
class Solution:
def fourSum(self, nums, target):
ans = []
nums.sort()
for i in range(len(nums)-2):
if i > 0 and nums[i] == nums[i-1]:
continue
for j in range(i+1,len(nums)-2):
if j > i+1 and nums[j] == nums[j-1]:
continue
b, e = j + 1, len(nums) - 1
while b < e:
diff = target - (nums[i] + nums[j] + nums[b] + nums[e])
if diff > 0:
b += 1
elif diff < 0:
e -= 1
else:
ans.append([nums[i], nums[j], nums[b], nums[e]])
while b < e and nums[b] == nums[b + 1]:
b += 1
while b < e and nums[e] == nums[e - 1]:
e -= 1
b += 1
e -= 1
return ans
discuss領域のpythonの最速コードは次のとおりです.
def fourSum(self, nums, target):
def findNsum(nums, target, N, result, results):
if len(nums) < N or N < 2 or target < nums[0]*N or target > nums[-1]*N: # early termination
return
if N == 2: # two pointers solve sorted 2-sum problem
l,r = 0,len(nums)-1
while l < r:
s = nums[l] + nums[r]
if s == target:
results.append(result + [nums[l], nums[r]])
l += 1
while l < r and nums[l] == nums[l-1]:
l += 1
elif s < target:
l += 1
else:
r -= 1
else: # recursively reduce N
for i in range(len(nums)-N+1):
if i == 0 or (i > 0 and nums[i-1] != nums[i]):
findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
results = []
findNsum(sorted(nums), target, 4, [], results)
return results
このコードコアも2 Sumのアルゴリズムを用い,再帰的に任意の数のNSum問題を解くことができる.しかし速度は120 msと速く、問題は重複数の判断を何度も少なくしたことだ.