对“求数组中所有和为某固定数的所有数对”的算法的简单思考

对“求数组中所有和为某固定数的所有数对”的算法的简单思考2011-09-30 博客园野文一、题目描述

有一个数组a[1000]，里面存放了1000个整数，请找出该数组中所有和为M的数对。例如数组为- 1,2,4,6,5,3,4,2,9,0,8,3，那么和为8的数对有（-1,9），（2,6），（4,4），（5,3），（5,3），（0,8）。

二、最普通的算法

在不可率复杂度的情况下，对于这个问题的最简单的算法如下：

private static List<int[]> UseNormalWay（int[] arr, int sumTotal）
         {
             List<int[]> result = new List<int[]>（）;
             for （int i = 0; i < arr.Length; i++）
             {
                 int expectNum = sumTotal - arr[i];
                 for （int j = i + 1; j < arr.Length; j++）
                 {
                     if （arr[j] == expectNum）
                     {
                         result.Add（new int[]{arr[i],  expectNum}）;
                     }
                 }
             }
             return result;
         }

利用两层循环查找所有和为固定数sumTotal的所有数对，将找到的数对存入List中。但是这个算法复杂度有点高，实际上在遍历的时候做了一些重复的工作：

1）后续循环的时候没有必要对前面已经配对的数列进行处理。

2）查找与某个数和为sumTotal的数时，应该可以有一些可以相互利用的过程。

基于这两点，可以引用一些01背包或动态规划的思想（或许引用得不恰当，我对这两种思想和理解很肤浅）来对这个算法进行改进，利用递归来操作。