流行的面试问题:
给定一个正整数数组和一个目标整数,找出是否存在连续的子数组其总和等于目标值。
例如:
数组 = [1,3,6,7,8,10]
目标值 = 16
总和等于16的子数组是[3,6,7]
,因此返回true。
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;
}
target
为 0
时,while
循环根本不会进入,且返回 acc == target
(即 true
)。因此,目标值为 0
时始终返回 true
。当我们将空子数组的和视为 0
时,这应该是正确的。 - Lingxi刚刚编写并完全测试。有两种方法:hasConsec(其中大部分逻辑)和sumArr(辅助方法,用于对数组中的值求和)。 hasConsec使用2个索引,第一个和最后一个创建子数组。使用helper方法对创建的子数组进行求和,然后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;
}
O(NlgN)
时间内对数组进行排序,但我没有看到任何排好序的数组有帮助的地方。 - Tim Biegeleisen