資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python - 來自兩個列表的 K 求和
列表是 Python 中一種重要的資料型別，可以儲存同構或異構資料的序列。它們是可變的。從兩個列表中查詢 K 求和意味著我們需要找到兩個列表元素的組合，其加和正好等於 K。在本文中，我們將首先探討暴力方法。接下來，我們將研究幾種最佳化的演算法，例如雙指標方法、雜湊演算法、列表推導式等。
使用暴力方法
暴力法是最簡單的方法。在這種方法中，我們在編寫邏輯時不考慮程式碼最佳化。為了找到 K 求和，我們可以使用兩個迴圈語句迭代列表並檢查元素的總和。如果總和等於 K，我們可以將元素附加到任何資料結構，例如列表。
示例
在下面的程式碼中，我們使用了暴力演算法。在 `k_sum_naive` 函式中，我們初始化了一個空列表。接下來，我們使用 for 迴圈迭代兩個列表，在每次迭代中，我們檢查兩個元素的總和是否等於 K。如果等於 K，我們將元素作為元組元素附加到已初始化的列表中。
def k_sum_naive(list1, list2, k):
result = []
for num1 in list1:
for num2 in list2:
if num1 + num2 == k:
result.append((num1, num2))
return result
list1 = [1, 2, 3, 4, 5]
list2 = [6, 7, 8, 9, 10]
k = 10
print(f'The first list is: {list1}')
print(f'The second list is: {list2}')
print(f'The required list is: {k_sum_naive(list1, list2, k)}')
輸出
The first list is: [1, 2, 3, 4, 5] The second list is: [6, 7, 8, 9, 10] The required list is: [(1, 9), (2, 8), (3, 7), (4, 6)]
時間複雜度：O(n^2)
空間複雜度：O(1)
使用雙指標方法
雙指標方法是一種流行的演算法技術，用於有效地解決各種問題。它涉及使用兩個指標（通常稱為“左”指標和“右”指標），它們同時從不同方向或速度遍歷陣列或列表。這種方法在處理需要查詢滿足特定條件的配對或子陣列的問題時特別有用。這種方法在許多流行的問題中很有用，例如檢測圖中的迴圈、滑動視窗問題、排序連結串列等。
示例
在下面的示例中，我們使用 `k_sum_two_pointer` 從兩個列表中返回 K 求和。在函式中，我們使用了 Python 的 `sort` 方法對列表進行排序。接下來，我們定義了兩個分別名為 `ptr1` 和 `ptr2` 的指標。我們迭代列表並將總和為 K 的元素附加到已初始化的列表中。
def k_sum_two_pointer(list1, list2, k):
list1.sort()
list2.sort()
result = []
ptr1, ptr2 = 0, len(list2) - 1
while ptr1 < len(list1) and ptr2 >= 0:
sum = list1[ptr1] + list2[ptr2]
if sum == k:
result.append((list1[ptr1], list2[ptr2]))
ptr1 += 1
ptr2 -= 1
elif sum < k:
ptr1 += 1
else:
ptr2 -= 1
return result
list1 = [1, 2, 3, 4, 5]
list2 = [12, 7, 8, 9, 10]
k = 13
print(f'The first list is: {list1}')
print(f'The second list is: {list2}')
print(f'The required list is: {k_sum_two_pointer(list1, list2, k)}')
輸出
The first list is: [1, 2, 3, 4, 5] The second list is: [12, 7, 8, 9, 10] The required list is: [(1, 12), (3, 10), (4, 9), (5, 8)]
時間複雜度：O(n log n)（由於排序）
空間複雜度：O(1)
使用雜湊方法
雜湊方法通常用於計算機科學和程式設計中，以高效地儲存、檢索和操作資料。它涉及使用雜湊函式將資料元素對映到唯一的識別符號，稱為雜湊值或程式碼。為了從列表中獲得 K 求和，我們可以採用以下演算法
我們可以維護一個雜湊表來插入任何列表中的所有數字。
接下來，我們可以迭代另一個列表，在每次迭代中，我們可以找到 K-element，其中 element 是第二個列表的元素。
現在，我們可以使用雜湊表查詢該值 (K-element) 是否存在於第一個列表中。如果存在，則數字的總和將等於 K，因此我們得到答案！
示例
在下面的程式碼中，我們建立了函式 `k_sum_hashing`，它使用列表和值 K 作為引數。我們初始化了一個名為 `hash_table` 的字典和一個名為 `result` 的列表。接下來，我們迭代第一個列表並使用雜湊將布林值 True 對映到現有元素。現在我們迭代第二個列表，在每次迭代中，我們找到 (K-num2) 的值，其中 num2 是第二個列表的元素。使用雜湊表，我們檢查該值是否存在於第一個列表中，如果存在，我們將數字附加到已初始化的列表中。
def k_sum_hashing(list1, list2, k):
hash_table = {}
result = []
for num1 in list1:
hash_table[num1] = True
for num2 in list2:
complement = k - num2
if complement in hash_table:
result.append((complement, num2))
return result
list1 = [1, 2, 3, 4, 5]
list2 = [12, 7, 8, 9, 10]
k = 13
print(f'The first list is: {list1}')
print(f'The second list is: {list2}')
print(f'The required list is: {k_sum_hashing(list1, list2, k)}')
輸出
The first list is: [1, 2, 3, 4, 5] The second list is: [12, 7, 8, 9, 10] The required list is: [(1, 12), (5, 8), (4, 9), (3, 10)]
時間複雜度：O(n)
空間複雜度：O(n)
使用列表推導式
列表推導式是 Python 中建立列表元素的一種流行方法。使用列表推導式的優點是我們可以輕鬆地將多個條件語句、迴圈等組合在一行中。但是，我們不能在列表推導式技術中編寫太多複雜的條件。
示例
在下面的程式碼中，我們使用列表推導式建立總和為 K 的對。我們建立了函式 `k_sum_list_comprehension`，它將列表和值 K 作為引數。在這個函式中，我們使用列表推導式來檢查列表中元素對的總和是否加起來等於 K。如果為真，我們將對附加到列表並返回它。
def k_sum_list_comprehension(list1, list2, k):
return [(num1, num2) for num1 in list1 for num2 in list2 if num1 + num2 == k]
list1 = [1, 2, 3, 4, 5]
list2 = [8,5,7,4]
k = 9
print(f'The first list is: {list1}')
print(f'The second list is: {list2}')
print(f'The required list is: {k_sum_list_comprehension(list1, list2, k)}')
輸出
The first list is: [1, 2, 3, 4, 5] The second list is: [8, 5, 7, 4] The required list is: [(1, 8), (2, 7), (4, 5), (5, 4)]
時間複雜度：O(n^2)
空間複雜度：O(1)
使用 Itertools 庫
Python 中的 itertools 庫提供了一種強大的方法來迭代可迭代物件。它提供了各種工具來處理涉及迭代器的常見程式設計任務，例如生成組合、排列和笛卡爾積。這是 Python 標準庫的一部分。我們可以利用 itertools 庫生成列表元素的組合，並使用自定義邏輯來檢查組合是否給出等於 K 的總和。
示例
在下面的程式碼中，我們首先匯入了 Python 的 itertools 庫。在 `k_suum_product` 函式中，我們使用 itertools 的 `product` 方法生成列表元素的組合。接下來，我們使用列表推導式檢查每個組合的元素總和是否等於 K。如果為真，我們將對附加到 `pairs` 列表中。
import itertools
def k_sum_product(list1, list2, k):
pairs = list(itertools.product(list1, list2))
return [(num1, num2) for (num1, num2) in pairs if num1 + num2 == k]
list1 = [1, 2, 3, 4, 5]
list2 = [8,5,7,4]
k = 9
print(f'The first list is: {list1}')
print(f'The second list is: {list2}')
print(f'The required list is: {k_sum_product(list1, list2, k)}')
輸出
The first list is: [1, 2, 3, 4, 5] The second list is: [8, 5, 7, 4] The required list is: [(1, 8), (2, 7), (4, 5), (5, 4)]
時間複雜度：O(n^2)
空間複雜度：O(n^2)
結論
在本文中，我們瞭解瞭如何在 Python 中處理來自兩個列表的 K 求和。我們可以構建自定義程式碼並使用 Python 中提供的庫。Python 預設情況下沒有任何庫來執行此函式，但它為我們提供了執行許多標準操作的方法，我們可以利用這些方法來解決問題。同時，暴力法、使用 Lambda 函式等更容易理解。它們需要更好的最佳化邏輯。因此，最好使用雜湊、雙指標等來解決問題。
瀏覽量：106
