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

(6)找到0和1个数相等的最大子数组

给定一个数组,它的元素是0和1,请找出最大的子数组,使这个子数组的元素中0和1的个数相等。

例如,输入
{ 0, 0, 1, 0, 1, 0, 0 }
输出
Largest subarray is { 0, 1, 0, 1 } or { 1, 0, 1, 0}

 

阅读全文 »

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

给定一个数组,它有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。

 

1. 通过Hash来计算

这种算法的思想是使用Hash来解决问题。在这个算法中,我们使用了一个辅助数组,数组中的元素是boolean类型,数组中元素的值用以表示某个值是否出现过。如果出现过,那么就返回true。
C++语言实现:

#include <iostream>
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n)
{
    // create an visited array of size n+1
    // we can also use map instead of visited array
    bool visited[n];
    fill(visited, visited + n, 0); // sets every value in the array to 0

    // for each element of the array mark it as visited and
    // return the element if it is seen before
    for (int i = 0; i < n; i++)
    {
        // if element is seen before
        if (visited[arr[i]])
            return arr[i];

        // mark element as visited
        visited[arr[i]] = true;
    }

    // no duplicate found
    return -1;
}

// main function
int main()
{
    // input array contains n numbers between [1 to n - 1]
    // with one duplicate
    int arr[] = { 1, 2, 3, 4, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Duplicate element is " << findDuplicate(arr, n);

    return 0;
}

Java语言实现:

class findDuplicate
{
    // Function to find a duplicate element in a limited range array
    public static int findDuplicate(int arr[])
    {
        // n is length of the array
        int n = arr.length;

        // create an visited array of size n+1
        // we can also use map instead of visited array
        boolean visited[] = new boolean[n + 1];

        // for each element of the array mark it as visited and
        // return the element if it is seen before
        for (int i = 0; i < n; i++)
        {
            // if element is seen before
            if (visited[arr[i]])
                return arr[i];

            // mark element as visited
            visited[arr[i]] = true;
        }

        // no duplicate found
        return -1;
    }

    // main function
    public static void main (String[] args)
    {
        // input array contains n numbers between [1 to n - 1]
        // with one duplicate
        int arr[] = { 1, 2, 3, 4, 4 };

        System.out.println("Duplicate element is " + findDuplicate(arr));
    }
}

输出: Duplicate element is 4

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(n)。

 

2

我们还能使用常量空间(空间复杂度为O(n))解决问你。既然数组中除了一个元素是重复之外,其他元素都是唯一的,并且元素的值在1到n-1之间,我们可以把数组的下标作为key,把元素取负数来判断元素是否重复。例如,队员每个元素arr[i],我们得到它的绝对值abs(arr[i]),并修改下标为abs(arr[i]) - 1的这个元素的正负号。最后,我们再遍历一次数组,如果第 i 个元素的值是正数,那么重复的元素就是 i + 1。

上面的算法我们遍历了2次数组。其实,我们可以缩为1次。对于每一个元素arr[i],我们得到绝对值abs(arr[i]),然后反转第abs(arr[i])-1个元素的符号,如果准备反转符号的元素已经是负数了,那么它一定是那个重复的数字。

C++语言实现:

#include <iostream>
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n)
{
    int duplicate = -1;

    // do for each element in the array
    for (int i = 0; i < n; i++)
    {
        // get absolute value of current element
        int absVal = (arr[i] < 0) ? -arr[i] : arr[i];

        // make element at index abs(arr[i])-1 negative if it is positive
        if (arr[absVal - 1] >= 0)
            arr[absVal - 1] = -arr[absVal - 1];
        else
        {
            // if element is already negative, it is repeated
            duplicate = absVal;
            break;
        }
    }

    // restore original array before returning
    for (int i = 0; i < n; i++)
    {
        // make negative elements positive
        if (arr[i] < 0)
            arr[i] = -arr[i];
    }

    // return duplicate element
    return duplicate;
}

// main function
int main()
{
    // input array contains n numbers between [1 to n - 1]
    // with one duplicate
    int arr[] = { 1, 2, 3, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Duplicate element is " << findDuplicate(arr, n);

    return 0;
}

java语言实现:

class findDuplicate
{
    // Function to find a duplicate element in a limited range array
    public static int findDuplicate(int arr[])
    {
        // n is length of the array
        int n = arr.length;

        int duplicate = -1;

        // do for each element in the array
        for (int i = 0; i < n; i++)
        {
            // get absolute value of current element
            int absVal = (arr[i] < 0) ? -arr[i] : arr[i];

            // make element at index abs(arr[i]) - 1 negative
            // if it is positive
            if (arr[absVal - 1] >= 0)
                arr[absVal - 1] = -arr[absVal - 1];
            else
            {
                // if element is already negative, it is repeated
                duplicate = absVal;
                break;
            }
        }

        // restore original array before returning
        for (int i = 0; i < n; i++)
        {
            // make negative elements positive
            if (arr[i] < 0)
                arr[i] = -arr[i];
        }

        // return duplicate element
        return duplicate;
    }

    // main function
    public static void main (String[] args)
    {
        // input array contains n numbers between [1 to n - 1]
        // with one duplicate
        int arr[] = { 1, 2, 3, 4, 4 };

        System.out.println("Duplicate element is " + findDuplicate(arr));
    }
}

输出: Duplicate element is 2

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(1)。

 

3. 使用异或

我们还可以使用异或(XOR)来解决问题。思路就是把所有的元素和1到n-1的数都异或一次,由于a^a = 0, 0^0 = 0,a^0 = a。在这个异或中,所有的元素都出现了2次,而重复的元素出现了3次,所以最后的值就是重复的元素。

C++语言实现:

#include <bits/stdc++.h>
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int A[], int n)
{
    int XOR = 0;

    // take xor of all array elements
    for (int i = 0; i < n; i++)
        XOR ^= A[i];

    // take xor of numbers from 1 to n-1
    for (int i = 1; i <= n-1; i++)
        XOR ^= i;

    // same elements will cancel out each other as a ^ a = 0,
    // 0 ^ 0 = 0 and a ^ 0 = a

    // xor will contain the missing number
    return XOR;
}

// main function
int main()
{
    // input array contains n numbers between [1 to n - 1]
    // with one duplicate
    int arr[] = { 1, 2, 3, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Duplicate element is " << findDuplicate(arr, n);

    return 0;
}

java语言实现:

class findDuplicate
{
    // Function to find a duplicate element in a limited range array
    public static int findDuplicate(int A[])
    {
        // n is length of the array
        int n = A.length;

        int XOR = 0;

        // take xor of all array elements
        for (int i = 0; i < n; i++)
            XOR ^= A[i];

        // take xor of numbers from 1 to n-1
        for (int i = 1; i <= n - 1; i++)
            XOR ^= i;

        // same elements will cancel out each other as a ^ a = 0,
        // 0 ^ 0 = 0 and a ^ 0 = a

        // xor will contain the missing number
        return XOR;
    }

    // main function
    public static void main (String[] args)
    {
        // input array contains n numbers between [1 to n - 1]
        // with one duplicate
        int arr[] = { 1, 2, 3, 4, 4 };

        System.out.println("Duplicate element is " + findDuplicate(arr));
    }
}

输出: Duplicate element is 2

这种方法时间复杂度是O(n),空间复杂度是O(1)。

 

4.求和

最后,我们可以通过求和的方式解决问题:先计算出所有元素的和,然后再减去1到n-1的和,最后的值就是重复的数。简单吧。:)

C++语言:

#include <numeric>
#include <iostream>
#include <array>

template <typename It>
int find_duplicate(It start, It finish)
{
    auto size = std::distance(start, finish);

    int actual_sum = std::accumulate(start, finish, 0);
    int expected_sum = size * (size - 1) / 2;

    return actual_sum - expected_sum;
}

int main()
{
    std::array<int, 5> arr1 = {{ 1, 2, 3, 4, 4 }};
    std::array<int, 5> arr2 = {{ 1, 2, 3, 4, 2 }};

    std::cout << "The duplicate element is " <<
                find_duplicate(arr1.begin(), arr1.end()) << '\n';

    std::cout << "The duplicate element is " <<
                find_duplicate(arr2.begin(), arr2.end()) << '\n';
}

输出:

The duplicate element is 4
The duplicate element is 2

这种方法时间复杂度是O(n),空间复杂度是O(1)。

(4/500)从有限范围的数组中找出重复元素

给定一个数组,它有n个元素,数组中包含1到n-1这些值。在这个数组中,除了一个元素是重复的,其他元素都只出现了一次。请找出重复的元素。

例如,
输入: { 1, 2, 3, 4, 4 }
输出:The duplicate element is 4

输入:{ 1, 2, 3, 4, 2 }
输出:The duplicate element is 2

 

1. 通过Hash来计算

这种算法的思想是使用Hash来解决问题。在这个算法中,我们使用了一个辅助数组,数组中的元素是boolean类型,数组中元素的值用以表示某个值是否出现过。如果出现过,那么就返回true。
C++语言实现:

#include <iostream>
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n)
{
    // create an visited array of size n+1
    // we can also use map instead of visited array
    bool visited[n];
    fill(visited, visited + n, 0); // sets every value in the array to 0

    // for each element of the array mark it as visited and
    // return the element if it is seen before
    for (int i = 0; i < n; i++)
    {
        // if element is seen before
        if (visited[arr[i]])
            return arr[i];

        // mark element as visited
        visited[arr[i]] = true;
    }

    // no duplicate found
    return -1;
}

// main function
int main()
{
    // input array contains n numbers between [1 to n - 1]
    // with one duplicate
    int arr[] = { 1, 2, 3, 4, 4 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Duplicate element is " << findDuplicate(arr, n);

    return 0;
}

Java语言实现:

class findDuplicate
{
    // Function to find a duplicate element in a limited range array
    public static int findDuplicate(int arr[])
    {
        // n is length of the array
        int n = arr.length;

        // create an visited array of size n+1
        // we can also use map instead of visited array
        boolean visited[] = new boolean[n + 1];

        // for each element of the array mark it as visited and
        // return the element if it is seen before
        for (int i = 0; i < n; i++)
        {
            // if element is seen before
            if (visited[arr[i]])
                return arr[i];

            // mark element as visited
            visited[arr[i]] = true;
        }

        // no duplicate found
        return -1;
    }

    // main function
    public static void main (String[] args)
    {
        // input array contains n numbers between [1 to n - 1]
        // with one duplicate
        int arr[] = { 1, 2, 3, 4, 4 };

        System.out.println("Duplicate element is " + findDuplicate(arr));
    }
}

输出: Duplicate element is 4

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(n)。

 

2

我们还能使用常量空间(空间复杂度为O(n))解决问你。既然数组中除了一个元素是重复之外,其他元素都是唯一的,并且元素的值在1到n-1之间,我们可以把数组的下标作为key,把元素取负数来判断元素是否重复。例如,队员每个元素arr[i],我们得到它的绝对值abs(arr[i]),并修改下标为abs(arr[i]) - 1的这个元素的正负号。最后,我们再遍历一次数组,如果第 i 个元素的值是正数,那么重复的元素就是 i + 1。

上面的算法我们遍历了2次数组。其实,我们可以缩为1次。对于每一个元素arr[i],我们得到绝对值abs(arr[i]),然后反转第abs(arr[i])-1个元素的符号,如果准备反转符号的元素已经是负数了,那么它一定是那个重复的数字。

C++语言实现:

#include <iostream>
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int arr[], int n)
{
    int duplicate = -1;

    // do for each element in the array
    for (int i = 0; i < n; i++)
    {
        // get absolute value of current element
        int absVal = (arr[i] < 0) ? -arr[i] : arr[i];

        // make element at index abs(arr[i])-1 negative if it is positive
        if (arr[absVal - 1] >= 0)
            arr[absVal - 1] = -arr[absVal - 1];
        else
        {
            // if element is already negative, it is repeated
            duplicate = absVal;
            break;
        }
    }

    // restore original array before returning
    for (int i = 0; i < n; i++)
    {
        // make negative elements positive
        if (arr[i] < 0)
            arr[i] = -arr[i];
    }

    // return duplicate element
    return duplicate;
}

// main function
int main()
{
    // input array contains n numbers between [1 to n - 1]
    // with one duplicate
    int arr[] = { 1, 2, 3, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Duplicate element is " << findDuplicate(arr, n);

    return 0;
}

java语言实现:

class findDuplicate
{
    // Function to find a duplicate element in a limited range array
    public static int findDuplicate(int arr[])
    {
        // n is length of the array
        int n = arr.length;

        int duplicate = -1;

        // do for each element in the array
        for (int i = 0; i < n; i++)
        {
            // get absolute value of current element
            int absVal = (arr[i] < 0) ? -arr[i] : arr[i];

            // make element at index abs(arr[i]) - 1 negative
            // if it is positive
            if (arr[absVal - 1] >= 0)
                arr[absVal - 1] = -arr[absVal - 1];
            else
            {
                // if element is already negative, it is repeated
                duplicate = absVal;
                break;
            }
        }

        // restore original array before returning
        for (int i = 0; i < n; i++)
        {
            // make negative elements positive
            if (arr[i] < 0)
                arr[i] = -arr[i];
        }

        // return duplicate element
        return duplicate;
    }

    // main function
    public static void main (String[] args)
    {
        // input array contains n numbers between [1 to n - 1]
        // with one duplicate
        int arr[] = { 1, 2, 3, 4, 4 };

        System.out.println("Duplicate element is " + findDuplicate(arr));
    }
}

输出: Duplicate element is 2

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(1)。

 

3. 使用异或

我们还可以使用异或(XOR)来解决问题。思路就是把所有的元素和1到n-1的数都异或一次,由于a^a = 0, 0^0 = 0,a^0 = a。在这个异或中,所有的元素都出现了2次,而重复的元素出现了3次,所以最后的值就是重复的元素。

C++语言实现:

#include <bits/stdc++.h>
using namespace std;

// Function to find a duplicate element in a limited range array
int findDuplicate(int A[], int n)
{
    int XOR = 0;

    // take xor of all array elements
    for (int i = 0; i < n; i++)
        XOR ^= A[i];

    // take xor of numbers from 1 to n-1
    for (int i = 1; i <= n-1; i++)
        XOR ^= i;

    // same elements will cancel out each other as a ^ a = 0,
    // 0 ^ 0 = 0 and a ^ 0 = a

    // xor will contain the missing number
    return XOR;
}

// main function
int main()
{
    // input array contains n numbers between [1 to n - 1]
    // with one duplicate
    int arr[] = { 1, 2, 3, 4, 2 };
    int n = sizeof(arr) / sizeof(arr[0]);

    cout << "Duplicate element is " << findDuplicate(arr, n);

    return 0;
}

java语言实现:

class findDuplicate
{
    // Function to find a duplicate element in a limited range array
    public static int findDuplicate(int A[])
    {
        // n is length of the array
        int n = A.length;

        int XOR = 0;

        // take xor of all array elements
        for (int i = 0; i < n; i++)
            XOR ^= A[i];

        // take xor of numbers from 1 to n-1
        for (int i = 1; i <= n - 1; i++)
            XOR ^= i;

        // same elements will cancel out each other as a ^ a = 0,
        // 0 ^ 0 = 0 and a ^ 0 = a

        // xor will contain the missing number
        return XOR;
    }

    // main function
    public static void main (String[] args)
    {
        // input array contains n numbers between [1 to n - 1]
        // with one duplicate
        int arr[] = { 1, 2, 3, 4, 4 };

        System.out.println("Duplicate element is " + findDuplicate(arr));
    }
}

输出: Duplicate element is 2

这种方法时间复杂度是O(n),空间复杂度是O(1)。

 

4.求和

最后,我们可以通过求和的方式解决问题:先计算出所有元素的和,然后再减去1到n-1的和,最后的值就是重复的数。简单吧。:)

C++语言:

#include <numeric>
#include <iostream>
#include <array>

template <typename It>
int find_duplicate(It start, It finish)
{
    auto size = std::distance(start, finish);

    int actual_sum = std::accumulate(start, finish, 0);
    int expected_sum = size * (size - 1) / 2;

    return actual_sum - expected_sum;
}

int main()
{
    std::array<int, 5> arr1 = {{ 1, 2, 3, 4, 4 }};
    std::array<int, 5> arr2 = {{ 1, 2, 3, 4, 2 }};

    std::cout << "The duplicate element is " <<
                find_duplicate(arr1.begin(), arr1.end()) << '\n';

    std::cout << "The duplicate element is " <<
                find_duplicate(arr2.begin(), arr2.end()) << '\n';
}

输出:

The duplicate element is 4
The duplicate element is 2

这种方法时间复杂度是O(n),空间复杂度是O(1)。

(3/500)在线性时间内对二进制数组排序

给定一个二进制数组(数组元素是0和1),请对数组进行排序,要求时间复杂度为O(n),空间复杂度为O(1)。输出内容应该是所有的0在前,之后是所有的1。
例如,
输入:{ 1, 0, 1, 0, 1, 0, 0, 1 }
输出:{ 0, 0, 0, 0, 1, 1, 1, 1 }

 

1. 傻瓜式方法

一种简单的方法是计算数组中0的个数(假设为k),然后把数组的前k个元素置为0,其他的置为1。同样道理,也可以计算1的个数(假设为k),然后把前面的k个元素置为1,其他的置为0。二者选一即可。实现方式比较简单,代码就省略了。

 

2. 填充0的另一种想法

和计算0的个数相比,我们可以换种方法。如果当前元素是0,我们可以把0放到下一个可用的位置。在所有的元素都处理了之后, 把其它所有的元素都置为1。

C++语言实现:

#include <bits/stdc++.h>
using namespace std;

// Function to sort binary array in linear time
int Sort(int A[], int n)
{
    // k stores index of next available position
    int k = 0;

    // do for each element
    for (int i = 0; i < n; i++)
    {
        // if current element is zero, put 0 at next free
        // position in the array
        if (A[i] == 0)
            A[k++] = 0;
    }

    // fill all remaining indexes by 1
    for (int i = k; i < n; i++)
        A[k++] = 1;
}

// main function
int main()
{
    int A[] = { 0, 0, 1, 0,1, 1, 0, 1, 0, 0 };
    int n = sizeof(A)/sizeof(A[0]);

    Sort(A, n);

    // print the rearranged array
    for (int i = 0 ; i < n; i++)
        cout << A[i] << " ";

    return 0;
}

java语言实现:

class SortBinaryArray
{
    // Function to sort binary array in linear time
    public static void Sort(int A[], int n)
    {
        // k stores index of next available position
        int k = 0;

        // do for each element
        for (int i = 0; i < n; i++)
        {
            // if current element is zero, put 0 at next free
            // position in the array
            if (A[i] == 0)
                A[k++] = 0;
        }

        // fill all remaining indexes by 1
        for (int i = k; i < n; i++)
            A[k++] = 1;
    }

    // main function
    public static void main (String[] args)
    {
        int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
        int n = A.length;

        Sort(A, n);

        // print the rearranged array
        for (int i = 0 ; i < n; i++)
            System.out.print(A[i] + " ");
    }
}

输出: 0 0 0 0 0 0 1 1 1 1

以上两种方案的时间复杂度都是O(n),空间复杂度都是o(1)。

 

3. 基于快速排序分而治之的算法

除了以上两种方法,我们还可以借用快速排序中分而治之的思想。这种方法的关键是使用1作为主元素(pivot element),然后创建一个分区过程,最后的结果就是排好序的。

C++语言实现:

#include <bits/stdc++.h>
using namespace std;

// Function to sort binary array in linear time
int Partition(int A[], int n)
{
    int pivot = 1;
    int j = 0;

    // each time we encounter a 0, j is incremented and
    // 0 is placed before the pivot
    for (int i = 0; i < n; i++)
    {
        if (A[i] < pivot)
        {
            swap(A[i], A[j]);
            j++;
        }
    }
}

// main function
int main()
{
    int A[] = { 1, 0, 0, 0, 1, 0, 1, 1 };
    int n = sizeof(A)/sizeof(A[0]);

    Partition(A, n);

    // print the rearranged array
    for (int i = 0 ; i < n; i++)
        cout << A[i] << " ";

    return 0;
}

java语言实现:

class SortBinaryArray
{
    // Function to sort binary array in linear time
    public static void Sort(int A[], int n)
    {
        int pivot = 1;
        int j = 0;

        // each time we encounter a 0, j is incremented and
        // 0 is placed before the pivot
        for (int i = 0; i < n; i++)
        {
            if (A[i] < pivot)
            {
                // swap (A[i], A[j])

                int temp = A[i];
                A[i] = A[j];
                A[j] = temp;

                j++;
            }
        }
    }

    // main function
    public static void main (String[] args)
    {
        int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
        int n = A.length;

        Sort(A, n);

        // print the rearranged array
        for (int i = 0 ; i < n; i++)
            System.out.print(A[i] + " ");
    }
}

输出: 0 0 0 0 0 0 1 1 1 1

尽管以上各种方法时间复杂度是O(n),空间复杂度是O(1),明显第三种方法的时间更少。

 

4. 通过首尾两个索引排序

我还能想到另外一种解决方案,新建两个索引分别指向首尾(head 和 end),向中间聚拢,当head指向的数字不为0,并且end指向的数字不为1时,交换它们的位置,直到head大于或等于end。

闲话少说,上代码。偷一下懒,我就只写Java代码了。

public class SortBinaryArray2 {

    // Function to sort binary array in linear time
    public static void Sort(int A[], int n)
    {
    	int head = 0;
    	int end = A.length - 1;

    	while( head < end )
    	{
    		while( A[head] == 0 && head < A.length -1 )
    		{
    			head ++;
    		}
    		while( A[end] == 1 && end > 0 )
    		{
    			end --;
    		}
    		if( head >= end )
    		{
    			break;
    		}
    		int temp = A[head];
    		A[head] = A[end];
    		A[end] = temp;
    	}
    }

	public static void main(String[] args) {
            int A[] = { 0, 0, 1, 0, 1, 1, 0, 1, 0, 0 };
            int n = A.length;

            Sort(A, n);

            // print the rearranged array
            for (int i = 0 ; i < n; i++)
            {
        	  System.out.print(A[i] + " ");
            }
	}
}

这种方法是不是更省时? ^_^

 

练习:
1. 在原方案的基础上修改方案,把1放在前面。
2. 给定一个数组,在线性时间内(时间复杂度为O(n))排序,使所有的偶数排在奇数之前。

(2/500)打印出和为0的所有子数组

给定一个整型数组,请打印出元素和为0的所有子数组。
例如,
输入:

{ 4, 2, -3, -1, 0, 4 }
输出:
Sub-arrays with 0 sum are
{ -3, -1, 0, 4 }
{ 0 }

输入:
{ 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }
输出:
Sub-arrays with 0 sum are
{ 3, 4, -7 }
{ 4, -7, 3 }
{ -7, 3, 1, 3 }
{ 3, 1, -4 }
{ 3, 1, 3, 1, -4, -2, -2 }
{ 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 }

 

1. 傻瓜式方法

傻瓜式方法的想法很简单,遍历数组的所有子数组,并计算它们的和。如果子数组的和等于0,那么就打印它。它的时间复杂度是 O(n3),因为一共有 n(n+1)/2(注:原文n2不对)个子数组,花费的时间是O(n2),然后还要花费 O(n)的时间求元素的和。当然,如果在找子数组的同时计算元素的和,那么这种方法可以优化成O(n2)时间。

C++语言实现:

#include <iostream>
#include <unordered_map>
using namespace std;

// Function to print all sub-arrays with 0 sum present
// in the given array
void printallSubarrays(int arr[], int n)
{
    // 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 so far
            sum += arr[j];

            // if sum is seen before, we have found a sub-array
            // with 0 sum
            if (sum == 0)
                cout << "Subarray [" << i << ".." << j << "]\n";
        }
    }
}

// main function
int main()
{
    int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
    int n = sizeof(arr)/sizeof(arr[0]);

    printallSubarrays(arr, n);

    return 0;
}

Java语言实现:

class PrintallSubarrays
{
    // Function to print all sub-arrays with 0 sum present
    // in the given array
    public static void printallSubarrays(int arr[])
    {
        // n is length of the array
        int n = arr.length;

        // 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 so far
                sum += arr[j];

                // if sum is seen before, we have found a sub-array with 0 sum
                if (sum == 0)
                    System.out.println("Subarray [" + i + ".." + j + "]");
            }
        }
    }

    // main function
    public static void main (String[] args)
    {
        int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
        printallSubarrays(arr);
    }
}

输出:
Subarray [0..2]
Subarray [0..9]
Subarray [1..3]
Subarray [2..5]
Subarray [3..9]
Subarray [5..7]

 

2. 使用map打印子数组

我们可以使用map打印所有和为0的子数组,子数组信息存放在另外的数组中并作为map的value。开始,我们创建一个空map存放所有和等于给定值的子数组的的结束下标。其中,key是和,value就是之前提到的另外一个数组,此数组中存放的就是和等于key的所有子数组的结束下标。我们遍历给定数组,在遍历过程中维护目前所遍历过的元素的和。如果元素的和在之前见过,那就意味着至少存在一个子数组和为0,子数组的结束下标就是当前遍历的下标,这样我们就能打印出所有的子数组。

C++语言实现:

#include <iostream>
#include <unordered_map>
using namespace std;

// Function to print all sub-arrays with 0 sum present
// in the given array
void printallSubarrays(int arr[], int n)
{
    // create an empty multi-map to store ending index of all
    // sub-arrays having same sum
    unordered_multimap<int, int> map;

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

    int sum = 0;

    // traverse the given array
    for (int i = 0; i < n; i++)
    {
        // sum of elements so far
        sum += arr[i];

        // if sum is seen before, there exists at-least one
        // sub-array with 0 sum
        if (map.find(sum) != map.end())
        {
            auto it = map.find(sum);

            // find all sub-arrays with same sum
            while (it != map.end() && it->first == sum)
            {
                cout << "Subarray [" << (it->second + 1) << ".." << i << "]\n";
                it++;
            }
        }

        // insert (sum so far, current index) pair into multi-map
        map.insert(pair<int, int>(sum, i));
    }
}

// main function
int main()
{
    int arr[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
    int n = sizeof(arr)/sizeof(arr[0]);
    printallSubarrays(arr, n);
    return 0;
}

java语言实现:

import java.util.HashMap;
import java.util.Map;
import java.util.ArrayList;

class PrintallSubarrays
{
    // Utility function to insert <key, value> into the Multimap
    private static void insert(Map<Integer, ArrayList> hashMap,
                                Integer key, Integer value)
    {
        // if key is already present
        if (hashMap.containsKey(key))
        {
            hashMap.get(key).add(value);
        }else
        // key is seen for the first time
        {
            ArrayList<Integer> list = new ArrayList<Integer>();
            list.add(value);
            hashMap.put(key, list);
        }
    }

    // Function to print all sub-arrays with 0 sum present
    // in the given array
    public static void printallSubarrays(int arr[])
    {
        // n is length of the array
        int n = arr.length;

        // create an empty Multi-map to store ending index of all
        // sub-arrays having same sum
        Map<Integer, ArrayList> hashMap = new
                                    HashMap<Integer, ArrayList>();

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

        int sum = 0;

        // traverse the given array
        for (int i = 0; i < n; i++)
        {
            // sum of elements so far
            sum += arr[i];

            // if sum is seen before, there exists at-least one
            // sub-array with 0 sum
            if (hashMap.containsKey(sum))
            {
                ArrayList<Integer> list = hashMap.get(sum);

                // find all sub-arrays with same sum
                for (Integer value: list) {
                    System.out.println("Subarray [" + (value + 1) + ".." +  i + "]");
                }
            }

            // insert (sum so far, current index) pair into the Multi-map
            insert(hashMap, sum, i);
        }
    }

    // main function
    public static void main (String[] args)
    {
        int A[] = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
        printallSubarrays(A);
    }
}

输出:
Subarray [0..2]
Subarray [1..3]
Subarray [2..5]
Subarray [5..7]
Subarray [3..9]
Subarray [0..9]

这样,只需遍历一次数组就能求出所有的子数组。

 

练习: 打印出和为非0的所有子数组。