是否有一個子目標與目標相加？

Question

受歡迎的訪談問題：

給定一個正整數和一個目標整數的數組，找出是否有一個連續的子數組與目標相加。

E.g.

陣列= [1,3,6,7,8,10] 目標= 16 求和至16是[3,6,7]，所以它返回真子陣列。

Answer 1

這是線性時間（C++代碼）。

bool Test(const int* arr, int size, int target) { 
    if (target < 0) return false; 
    int acc = 0; 
    int i = 0, j = 0; 
    while (acc != target) { 
    if (acc < target) { 
     if (j == size) break; 
     acc += arr[j++]; 
    } 
    else { 
     acc -= arr[i++]; 
    } 
    } 
    return acc == target; 
} 

注意，預檢查爲陰性目標值是必要的，以保證循環不變的是i <= j。具體而言，當i == j,acc將是0，並且正目標保證if (acc < target)下的分支被命中。

Answer 2

剛剛寫完並經過充分測試。 hasConsec（其中大部分邏輯是）和sumArr（在數組中求和值的幫助器方法）兩種方法。 hasConsec並使用2個索引（第一個和最後一個）創建子陣列。輔助方法用於對創建的子數組進行求和，然後hasConsec檢查它是否與目標匹配，是否大於目標，或者是否小於目標。如果匹配，則返回true;如果總和小於目標，則最後一個索引增加;如果它大於目標，則第一個索引增加。重複，直到第一個索引等於數組的長度。如果發生這種情況，則不會有子目標與目標相加。返回false;

public static boolean hasConsec(int arr[], int target) { 
    int first = 0, last = 0; 

    while (last < arr.length) { 
     int sub[] = Arrays.copyOfRange(arr, first, last); 
     int subSum = sumArr(sub); 
     if (subSum == target) 
      return true; 
     else if (subSum < target) 
      last++; 
     else { 
      if (++first < last) 
       last = first; 
     } 
    } 
    return false; 
} 

public static int sumArr(int arr[]) { 
    int sum = 0; 
    for (int i = 0; i < arr.length; i++) 
     sum += arr[i]; 
    return sum; 
}