Python數組中求和問題

本專題主要介紹哈希表和指針兩種方法來解決該類問題，從兩個數之和引申到三個數之和，再從四個數之和的問題上思考如何建構出一種通用的代碼（可以解決N個數之和）。本文主要内容是通過001問題來初步了解數組求和的兩種常用方法。

001-Two Sum

給定一個整數數組和一個目标值，找出數組中和為目标值的兩個數。 你可以假設每個輸入隻對應一種答案，且同樣的元素不能被重複利用。

示例 :

給定 nums = [2, 7, 11, 15], target = 9

因為 nums[0] + nums[1] = 2 + 7 = 9 是以傳回 [0, 1]

1. 暴力循環

O(n^2)

唯一需要注意的是同一個元素不能複用

nums_len = len(nums)
for
 i 
in
 range(
0
, nums_len):
    
for
 j 
in
 range(i + 
1
, nums_len):
        
if
 nums[i] + nums[j] == target:
            
return
 [i, j]
           

1. 哈希

（1） O（n）

（2） 考慮暴力循環中我們做的事情，我們先挑出一個值a，然後看數組中其他值是否能與值a相加等于目标，也可以說成看數組中是否存在一個值等于目标值減去值a。

（3） 換個思路，我們将所有周遊過的值存放起來，每次周遊到一個新的值b時，我們可以查找目标值減去值b是否在我們存放的值中。基于哈希表的特性，查找的時間複雜度為O（1），總時間複雜度就變為了一次for循環O（n）

回到本道題中:

（1） 由于需要傳回對應的索引，是以需要使用HashMap（在python中是dict），key存放數組中的值，value存放數組中的索引，周遊數組，将周遊過的值存入dict，如果目标值減去目前值在dict中則證明找到了目标值。

（2） 還有一點需要注意的是如果想按從小到大的順序傳回值，dict中存放的肯定是前一個值（因為是之前周遊過的）。

seen_dict = {} 
for
 i, num 
in
 enumerate(nums):
    search = target - num
    
if
 search 
in
 seen_dict:
        
return
 [seen_dict[search], i]
    
else
:
        seen_dict[num] = i
           

1. 雙指針

（1） O(nlogn)-主要是快排的影響

（2） 在一個有序的數組中最左邊一定是最小值，而最右邊一定是最大值。我們可以将最小值與最大值相加與目标值進行比較，如果兩數之和大于目标值，我們就讓最大值小一點（也就是讀取第二個最大值），相反如果小于，則讓最小值大一點（讀取第二個最小值）。這樣我們就保證了一次循環就能查找到目标值，但數組必須是有序的。

回到題目中:

（1） 由于需要傳回索引，是以我們必須存儲兩個數組，一個是無序的（用于查找真實的索引），另一個是有序的（用于查找符合題目的值）。

（2） 兩個指針left和right分别指向數組中第一個元素和最後一個元素（最小值和最大值）

（3） 循環的結束條件為左指針大于等于右指針（左邊的不能比右邊的大，而且一個元素隻能用一次）

（4） 然後就判斷左值+右值與目标值之間的關系，在上面我們已經讨論過了大于和小于的情況。

（5） 當等于時由于我們需要得到左值和右值在原本數組的索引，我們需要考慮以下問題。從題目中的得知每個target隻有一個答案, 意味着如果target是6不會出現[2, 2, 4]的情況, 但是會出現[3, 3]的情況, 也就是當兩個相同的值滿足情況是才會有重複的元素。是以我們先通過index擷取左值對應的索引，如果左值和右值相同我們就擷取下一個該值的索引，如果不同，我們直接擷取右值相關的索引。

raw_nums = nums
nums = sorted(nums)
left, right = 
0
, len(nums) - 
1
   
while
 left < right:
    v_left, v_right = nums[left], nums[right]
    two_sum = v_left + v_right
    
if
 two_sum > target:
        right -= 
1
    
elif
 two_sum < target:
        left += 
1
    
else
:  
# 找到了
        left_index = raw_nums.index(v_left)
        
# 如果值相同就查找下一個該值的索引
        right_index = raw_nums.index(v_right, left + 
1
) 
if
 v_right == v_left 
else
 raw_nums.index(v_right)
        
return
 [left_index, right_index]
           

總結

通過兩個數求和問題初步了解數組求和問題，下一文将引申這兩種方法在三個數求和中的應用。

原文釋出時間為：2018-08-04

本文作者：dyq666

本文來自雲栖社群合作夥伴“

Python中文社群

”，了解相關資訊可以關注“

”