最近我遇到了这个 C 代码来查找数组中等于总和的整数。
int subArraySum(int arr[], int n, int sum)
{
/* Initialize curr_sum as value of first element
and starting point as 0 */
int curr_sum = arr[0], start = 0, i;
/* Add elements one by one to curr_sum and if the curr_sum exceeds the
sum, then remove starting element */
for (i = 1; i <= n; i++)
{
// If curr_sum exceeds the sum, then remove the starting elements
while (curr_sum > sum && start < i-1)
{
curr_sum = curr_sum - arr[start];
start++;
}
// If curr_sum becomes equal to sum, then return true
if (curr_sum == sum)
{
printf ("Sum found between indexes %d and %d", start, i-1);
return 1;
}
// Add this element to curr_sum
if (i < n)
curr_sum = curr_sum + arr[i];
}
// If we reach here, then no subarray
printf("No subarray found");
return 0;
}
我的问题是，该算法的运行时间为 O(n)，这可以通过计算在最坏情况下对 arr[] 的每个元素执行的操作数来证明。据我所知，它看起来像一个 O(n^2) 算法。可能是我错过了学习的东西，但任何人都可以解释这是 O(n)，如果这完全是 O(n)。