本站首页 返回顶部 关于博主

(5)找到和等于给定值的最长子数组

PDF版

给定一个数组,它有n个元素,元素类型为整形。给定一个值,如果能找出1到多个子数组,使子数组中所有元素的和等于给定值。请求出这个多个子数组中最长的那个子数组。

例如,给定如下数组和值:
A[] = { 5, 6, -5, 5, 3, 5, 3, -2, 0 }
Sum = 8

那么,和为8的子数组有3个,分别是:
{ -5, 5, 3, 5 }
{ 3, 5 }
{ 5, 3 }

其中,最长的子数组是
{ -5, 5, 3, 5 },它的长度为4。

 

一种最直接的方法就是遍历所有的子数组,并求出它们的和。如果子数组的和等于给定值,那么我们就更新最长子数组的值。这种方法的时间复杂度是O(n3),因为有n2个子数组,按后还要花O(n)时间求出它所有元素的和。当然,如果把计算子数组的和优化成O(1),那么这种方法的时间复杂度可以优化成O(n2)

C++语言实现


#include
#include
using namespace std;

// Naive function to find maximum length sub-array with sum S present
// in the given array
void maxLengthSubArray(int arr[], int n, int S)
{
// len stores the maximum length of sub-array with sum S
int len = 0;

// stores ending index of maximum length sub-array having sum S
int ending_index = -1;

// consider all sub-arrays starting from i
for (int i = 0; i < n; i++) { int sum = 0; // consider all sub-arrays ending at j for (int j = i; j < n; j++) { // sum of elements in current sub-array sum += arr[j]; // if we have found a sub-array with sum S if (sum == S) { // update length and ending index of max length sub-array if (len < j - i + 1) { len = j - i + 1; ending_index = j; } } } } // print the sub-array cout << "[" << (ending_index - len + 1) << "," << ending_index << "]"; } // main function int main() { int arr[] = { 5, 6, -5, 5, 3, 5, 3, -2, 0 }; int sum = 8; int n = sizeof(arr)/sizeof(arr[0]); maxLengthSubArray(arr, n, sum); return 0; } [/cpp] Java语言实现: [java] class MaxLengthSubArray { // Naive function to find maximum length sub-array with sum S present // in the given array public static void maxLengthSubArray(int arr[], int S) { // n is length of the array int n = arr.length; // len stores the maximum length of sub-array with sum S int len = 0; // stores ending index of maximum length sub-array having sum S int ending_index = -1; // consider all sub-arrays starting from i for (int i = 0; i < n; i++) { int sum = 0; // consider all sub-arrays ending at j for (int j = i; j < n; j++) { // sum of elements in current sub-array sum += arr[j]; // if we have found a sub-array with sum S if (sum == S) { // update length & ending index of max length subarray if (len < j - i + 1) { len = j - i + 1; ending_index = j; } } } } // print the sub-array System.out.println("[" + (ending_index - len + 1) + ", " + ending_index + "]"); } // main function public static void main (String[] args) { int arr[] = { 5, 6, -5, 5, 3, 5, 3, -2, 0 }; int sum = 8; maxLengthSubArray(arr, sum); } } [/java] 输出:
[2,5]

2

我们还可以使用map来解决这个问题,使时间复杂度降低到O(n)。这种方法的思想是:先创建一个空Map,然后用它存储所有第一个和(设为Sum)等于给定值的子数组的下标。我们遍历数组,然后维护便利过的元素的Sum。如果和是第一次碰到,然后把Sum与它的下标插入到数组中。如果(Sum-S)在之前碰到过,意味着存在一个子数组,它的和(Sum)等于给定值,它的结束下标就是当前下标。如果当前数组的长度更长,那么我就需要更新和等于S的最大子数组的长度。

C++语言实现:


#include
using namespace std;

// Function to find maximum length sub-array with sum S present
// in the given array
void maxLengthSubArray(int arr[], int n, int S)
{
// create an empty map to store ending index of first sub-array
// having some sum
unordered_map map;

// insert (0, -1) pair into the set to handle the case when
// sub-array with sum S starts from index 0
map[0] = -1;

int sum = 0;

// len stores the maximum length of sub-array with sum S
int len = 0;

// stores ending index of maximum length sub-array having sum S
int ending_index = -1;

// traverse the given array
for (int i = 0; i < n; i++) { // sum of elements so far sum += arr[i]; // if sum is seen for first time, insert sum with its index // into the map if (map.find(sum) == map.end()) map[sum] = i; // update length and ending index of maximum length sub-array // having sum S if (map.find(sum - S) != map.end() && len < i - map[sum - S]) { len = i - map[sum - S]; ending_index = i; } } // print the sub-array cout << "[" << (ending_index - len + 1) << "," << ending_index << "]"; } int main() { int arr[] = { 5, 6, -5, 5, 3, 5, 3, -2, 0 }; int sum = 8; int n = sizeof(arr) / sizeof(arr[0]); maxLengthSubArray(arr, n, sum); return 0; } [/cpp] java语言实现: [java] import java.util.Map; import java.util.HashMap; class MaxLengthSubArray { // Naive function to find maximum length sub-array with sum S present // in the given array public static void maxLengthSubArray(int arr[], int S) { // n is length of the array int n = arr.length; // create an empty Hash Map to store ending index of first // sub-array having some sum Map map = new HashMap();

// insert (0, -1) pair into the set to handle the case when
// sub-array with sum S starts from index 0
map.put(0, -1);

int sum = 0;

// len stores the maximum length of sub-array with sum S
int len = 0;

// stores ending index of maximum length sub-array having sum S
int ending_index = -1;

// traverse the given array
for (int i = 0; i < n; i++) { // sum of elements so far sum += arr[i]; // if sum is seen for first time, insert sum with its index // into the map if (!map.containsKey(sum)) map.put(sum, i); // update length and ending index of maximum length sub-array // having sum S if (map.containsKey(sum - S) && len < i - map.get(sum - S)) { len = i - map.get(sum - S); ending_index = i; } } // print the sub-array System.out.println("[" + (ending_index - len + 1) + ", " + ending_index + "]"); } // main function public static void main (String[] args) { int arr[] = { 5, 6, -5, 5, 3, 5, 3, -2, 0 }; int sum = 8; maxLengthSubArray(arr, sum); } } [/java] 输出: [2,5]

以上方案的时间复杂度和空间复杂度都是o(n)。




请你留言

Protected with IP Blacklist CloudIP Blacklist Cloud