给定一个整型数组，请打印出元素和为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(n³)，因为一共有 n(n+1)/2(注：原文n²不对)个子数组，花费的时间是O(n²)，然后还要花费 O(n)的时间求元素的和。当然，如果在找子数组的同时计算元素的和，那么这种方法可以优化成O(n²)时间。

C++语言实现：

java语言实现：

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

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

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

给定一个整型数组，数组未排序，请找出一对数，使这两个数的和等于一个给定的值。
例如，
输入:
arr = [8, 7, 2, 5, 3, 1]
sum = 10

输出:
Pair found at index 0 and 2 (8 + 2)
或
Pair found at index 1 and 4 (7 + 3)

1. 傻瓜式方法

傻瓜式方法比较粗暴，通过遍历给定数组中的所有两个数字组成的组合，只要发现一个组合的和等于期望中的数字，就返回它们。

C语言实现：

#include

// Naive method to find a pair in an array with given sum
void findPair(int arr[], int n, int sum)
{
// consider each element except last element
for (int i = 0; i < n - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < n; j++) { // if desired sum is found, print it and return if (arr[i] + arr[j] == sum) { printf("Pair found at index %d and %d", i, j); return; } } } // No pair with given sum exists in the array printf("Pair not found"); } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } [/c] 下载代码 运行代码

Java语言实现：

class FindPair
{
// Naive method to find a pair in an array with given sum
public static void findPair(int arr[], int sum)
{
// n is length of the array
int n = arr.length;

// consider each element except last element
for (int i = 0; i < n - 1; i++) { // start from i'th element till last element for (int j = i + 1; j < n; j++) { // if desired sum is found, print it and return if (arr[i] + arr[j] == sum) { System.out.println("Pair found at index " + i + " and " + j); return; } } } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } } [/java] 下载代码 运行代码

输出：
Pair found at index 0 and 2

这种解决方案的时间复杂度是 O(n²)，空间复杂度是 O(1)。

2. 使用排序复杂度为O(nlogn)的方法

这种方法的观点是，先对数组进行排序，然后通过两个索引index（高high和低low）来进行搜索。在初始状态时，这两个索引index分别指向数组的首尾（假设数组长度为n，low指向第0个元素，high指向第n-1个元素）。然后我们不断地逼近low和high的值来搜索数组arr[low…high]，直到low大于或等于high。在这个过程中，我们计算arr[high]与arr[low]之和，并与给定的数字比较，如果和小于给定数字，就增加low的值，反之则减少high的值。最后，如果在数组中找到了这一对数字，返回它们即可。

C++语言实现：

#include

// Function to find a pair in an array with given sum using Sorting
void findPair(int arr[], int n, int sum)
{
// sort the array in ascending order
std::sort(arr, arr + n);

// maintain two indexes pointing to end-points of the array
int low = 0;
int high = n – 1;

// reduce search space arr[low..high] at each iteration of the loop

// loop till low is less than high
while (low < high) { // sum found if (arr[low] + arr[high] == sum) { std::cout << "Pair found"; return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum (arr[low] + arr[high] < sum)? low++: high--; } // No pair with given sum exists in the array std::cout << "Pair not found"; } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } [/cpp] 下载代码 运行代码

java语言实现：

import java.util.Arrays;

class FindPair
{
// Naive method to find a pair in an array with given sum
public static void findPair(int arr[], int sum)
{
// sort the array in ascending order
Arrays.sort(arr);

// maintain two indexes pointing to end-points of the array
int low = 0;
int high = arr.length – 1;

// reduce search space arr[low..high] at each iteration of the loop

// loop till low is less than high
while (low < high) { // sum found if (arr[low] + arr[high] == sum) { System.out.println("Pair found"); return; } // increment low index if total is less than the desired sum // decrement high index is total is more than the sum if (arr[low] + arr[high] < sum) low++; else high--; } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } } [/java] 下载代码 运行代码

输出:
Pair found

这种解决方案的时间复杂度是 O(nlogn)，空间复杂度是 O(1)。

3. 使用Map复杂度为O(n)的方法

其实，我们可以在线性的时间内解决问题，解决方案的关键在于使用map。算法就是把数组中的元素arr[i]插入到map中。在遍历数组过程中，我们需要查找sum – arr[i]是否在数组中。如果能找到，就打印出arr[i]和sum-array[i]，返回。

C++语言实现：

#include
using namespace std;

// Function to find a pair in an array with given sum using Hashing
void findPair(int arr[], int n, int sum)
{
// create an empty map
unordered_map map;

// do for each element
for (int i = 0; i < n; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.find(sum - arr[i]) != map.end()) { cout << "Pair found at index " << map[sum - arr[i]] << " and " << i; return; } // store index of current element in the map map[arr[i]] = i; } // we reach here if pair is not found cout << "Pair not found"; } // main function int main() { int arr[] = { 8, 7, 2, 5, 3, 1}; int sum = 10; int n = sizeof(arr)/sizeof(arr[0]); findPair(arr, n, sum); return 0; } [/cpp] 下载代码 运行代码

java语言实现：

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

class FindPair
{
// Naive method to find a pair in an array with given sum
public static void findPair(int arr[], int sum)
{
// create an empty Hash Map
Map map = new HashMap();

// do for each element
for (int i = 0; i < arr.length; i++) { // check if pair (arr[i], sum-arr[i]) exists // if difference is seen before, print the pair if (map.containsKey(sum - arr[i])) { System.out.println("Pair found at index " + map.get(sum - arr[i]) + " and " + i); return; } // store index of current element in the map map.put(arr[i], i); } // No pair with given sum exists in the array System.out.println("Pair not found"); } // main function public static void main (String[] args) { int arr[] = { 8, 7, 2, 5, 3, 1 }; int sum = 10; findPair(arr, sum); } } [/java] 下载代码 运行代码

输出：
Pair found at index 0 and 2

这种方案的时间复杂度和空间复杂度都是O(n)。

练习： 打印出数组中所有和等于给定值的数字对。

既然决定开始让自己坚持写作，那就从翻译《数据结构与算法500例》开始吧。一方面，这500个例子对巩固算法能力、扩展思维有很大的帮助；另一方面，对我而言，它难度不大，占用时间不多，容易坚持下来。

这500例的英文原文来自：500 Data Structures and Algorithms practice problems and their solutions