Two sum 最簡單的就是用窮舉法把所有的組合都列出來，時間複雜度為 O(n^2)，而且一直到 n sum 都可以使用這樣的方式來做。當然就是時間複雜度太高了。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
for j in range(i+1, len(nums)):
if nums[i] + nums[j] == target:
return [i, j]
return [-1, -1]
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
def helper(numbers: List[int], target: int):
lo = 0
hi = len(numbers) - 1
while lo < hi:
s = nums[lo] + nums[hi]
if s < target:
lo += 1
elif s > target:
hi -= 1
else: # s == target
res.append([left, right])
return res
numbers.sort()
return helper(numbers, target)
於是這樣就可以開始擴展當 n > 2 的時候， 該怎麼辦呢？
當 n == 1 的時候，沒有所謂的總和問題，所以答案為空集合。
當 n == 2 的時候，就是所謂的 2 Sum ，可以透過上方的方式找到
當 n == 3 的時候，是不是可以把設定的目標先剪去第一個陣列中的第 i 個數字，得到一個新目標，接著在剩下的兩個陣列中，用新的目標找 2 Sum 。
...
當 n == k 的時候，就可以推導出，先將目標減去第一個陣列中的第 i 個數字，得到一個新目標後，在接下來的 k - 1 個陣列中，找出 k-1 Sum 。
所以我們就找到了基本情況， n == 1 與 n == 2，並且可以透過遞迴的方式來找出 nSum 。
class Solution:
def twoSum(self, nums: List[int], start: int, target: int) -> List[List[int]]:
lo = start
hi = len(nums) - 1
res = []
while lo < hi:
left = nums[lo]
right = nums[hi]
s = nums[lo] + nums[hi]
if s < target:
lo += 1
elif s > target:
hi -= 1
else: # s == target
res.append([left, right])
while (lo < hi and left == nums[lo]):
lo += 1
while (lo < hi and right == nums[hi]):
hi -= 1
return res
def kSum(self, k, nums, target, start):
size = len(nums)
res = []
if n < 2 or size < k:
return res
if n == 2:
return self.twoSum(nums, start, target)
else:
i = start
while i < size:
tuples = self.kSum(nums, k - 1, i + 1, target - nums[i])
for tup in tuples:
tup.append(nums[i])
res.append(tup)
while i < size - 1 and nums[i] == nums[i + 1]:
i += 1
i += 1
return res
def nSum(self, nums: List[int], target: int, n: int) -> List[List[int]]:
# 先一開始就將陣列排序
nums.sort()
return self.kSum(n, nums, target, 0)
而 nSum 其實還有另外一個觀念還沒有寫到，那就是利用 Hash Table ，讓我們重回到 2 Sum ，2 Sum 是 LeetCode 的天字第一號題目，又是一個超高頻的題目，我想幾乎每個人都會，雙指針的方式在原始的 2 Sum 題目裡面，其實不是最有效率的，另一個方法不會太難，儘管是簡單的題目，但我在第一次刷題的時候，記得想出這個方法的時候心裡還是有一種「哇！原來這就是刷題的感覺啊，所有的東西我都會，都很常用，但是第一次要把他們用在一起的時候，是沒辦法瞬間做到的」
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
table = {}
for i in range(len(nums)):
num = nums[i]
if target - num in table:
return [table[target - num], i]
else:
table[num] = i
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
table = {}
ans = 0
for num1 in nums1:
for num2 in nums2:
s = num1 + num2
table[s] = table.get(s, 0) + 1
for num3 in nums3:
for num4 in nums4:
s = num3 + num4
if -s in table:
ans += table.get(-s, 0)
return ans
可以稍微的整理一下，變成不一定要是只能是 0 任意目標，任意目標皆可
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
def helper(nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int], target: int):
table = {}
ans = 0
for num1 in nums1:
for num2 in nums2:
s = num1 + num2
table[s] = table.get(s, 0) + 1
for num3 in nums3:
for num4 in nums4:
s = num3 + num4
if target-s in table:
ans += table.get(target-s, 0)
return ans
return helper(nums1, nums2, nums3, nums4, 0)