本站首页 返回顶部 关于博主
« (1/500)找出和等于给定值的两个数
(3/500)在线性时间内对二进制数组排序 »

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

PDF版

给定一个整型数组，请打印出元素和为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++语言实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#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&#91;j&#93;;
  
            // if sum is seen before, we have found a sub-array
            // with 0 sum
            if (sum == 0)
                cout << "Subarray &#91;" << i << ".." << j << "&#93;\n";
        }
    }
}
  
// main function
int main()
{
    int arr&#91;&#93; = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
    int n = sizeof(arr)/sizeof(arr&#91;0&#93;);
  
    printallSubarrays(arr, n);
  
    return 0;
}
&#91;/cpp&#93;
 
 
Java语言实现：
&#91;java&#93;class PrintallSubarrays
{
    // Function to print all sub-arrays with 0 sum present
    // in the given array
    public static void printallSubarrays(int arr&#91;&#93;)
    {
        // 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&#91;j&#93;;
      
                // if sum is seen before, we have found a sub-array with 0 sum
                if (sum == 0)
                    System.out.println("Subarray &#91;" + i + ".." + j + "&#93;");
            }
        }
    }
  
    // main function
    public static void main (String&#91;&#93; args)
    {
        int arr&#91;&#93; = { 3, 4, -7, 3, 1, 3, 1, -4, -2, -2 };
        printallSubarrays(arr);
    }
}&#91;/java&#93;
 
<strong>输出：</strong><span style="font-family: consolas; font-size: small;">
Subarray [0..2]
Subarray [0..9]
Subarray [1..3]
Subarray [2..5]
Subarray [3..9]
Subarray [5..7]</span>
 
<br>
<div style="background-color: #99CCFF; height: 1px;"></div>
<h3>2. 使用map打印子数组</h3>
我们可以使用map打印所有和为0的子数组，子数组信息存放在另外的数组中并作为map的value。开始，我们创建一个空map存放所有和等于给定值的子数组的的结束下标。其中，key是和，value就是之前提到的另外一个数组，此数组中存放的就是和等于key的所有子数组的结束下标。我们遍历给定数组，在遍历程中维护目前所遍历过的元素的和。如果元素的和在之前见过，那就意味着至少存在一个子数组和为0，子数组的结束下标就是当前遍历的下标，这样我们就能打印出所有的子数组。
 
C++语言实现：
[cpp]
#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&#91;i&#93;;
  
        // 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 &#91;" << (it->second + 1) << ".." << i << "&#93;\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语言实现：

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
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&#91;i&#93;;
      
            // 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的所有子数组。



|      2017年05月08日 星期一  06:55:06| 算法设计| 添加评论|


请你留言

Protected with IP Blacklist CloudIP Blacklist Cloud