数据结构与算法--有序数组中找出和为s的两个数字

冷不防 2022-10-11 01:15 29阅读 0赞

#### 有序数组中找和为s的两个数字 ####

*  题目：输入一个递增排序的数组array， 和一个数字s， 在数组中找出两个数，使得这两个数的和是s，如果有多对，输出一对即可。

##### 最简单方案 #####

*  双循环，每次获取一个数据，和数组中其他数据求和，与s比较，此方法最直观，时间复杂度是O(n2)，比如必然会有更优解

##### 优化方案一 #####

*  既然要找两个数字，而且是数组，第一感觉就是双指针的策略，分析如下
    
     *  既然要找两个数字，那么假如我们随机选两个，如果和小于s，那么应该向后找，反之向前找
     *  案例分析法\{1,2，4,7，11,15\}，找和为15 的
     *  初始化两个指针分别指向 最后元素positionBig，指向第一个元素 positionSmall
     *  如果两个数据和正好是s，那么得到解
     *  如果两个数据和大于s，说明需要减少，那么应该positionBig –
     *  如果两个数据和小于s，说明需要增大，那么应该positionSmall++
     *  如下图：  
        ![在这里插入图片描述][20210705174112468.png]
 *  如上分析有如下代码

/** * 在有序数组中查找和为 s的两个数字 * @author liaojiamin * @Date:Created in 17:38 2021/6/29 */
    public class FindSumInSortArray { 
    
        public static void main(String[] args) { 
            int[] array = new int[]{ 1,2,3,7,8,11,14,16,17,18,23,47,59,67,79,83,222,344,556,778};
            System.out.println(findSumNum(array, 111));
        }
        /** * 找出递增排序数组中的两个数字，使得这两个数字的和为 s * */
        public static boolean findSumNum(int[] array, int s){ 
            if(array == null || array.length <= 0){ 
                return false;
            }
            int positionBig = array.length -1;
            int positionSmall = 0;
            while (array[positionBig] + array[positionSmall] != s){ 
                if(positionBig < positionSmall){ 
                    return false;
                }
                if(array[positionBig] + array[positionSmall] > s){ 
                    positionBig --;
                }
                if(array[positionBig] + array[positionSmall] < s){ 
                    positionSmall++;
                }
            }
            System.out.println(array[positionSmall] + " + "+ array[positionBig] +" = "+ s);
            return true;
        }
    }

*  如上代码中我们while循环的退出条件是 positionBig< positionSmall那么我们总共应该就是一次循环，时间福再度是O(n)，不使用额外空间

#### 变种题型，非有序数组 ####

*  题目：输入一个非有序数组array， 和一个数字s， 在数组中找出两个数的组合，使得这两个数的和是s，如果有多对，输出多对即可。
 *  因为没有了有序的特性，我们无法用上题中的方案，最简单办法，先排序，在按上面的方法，这样时间复杂度比如超过O(n)
 *  另一中思路，空间换时间：
    
     *  遍历数组，并且将数组已经遍历过的值k 存储在hash中，存储模式为 key = k， value = k，这样可以用O(1)的时间拿到已经范问过的数据
     *  每次遍历数组中数据 n 时候，查找hash中 s-n
     *  如果s-n 存在，那么在之前遍历过的数据中存在与n 配对后和为s的数据，一次遍历完数据，找到我们需要的所有配对：

/** * 非有序数组中找出和为s的两个数 * */
        public static boolean findSumInList(int[] array, int s){ 
            if(array == null || array.length <= 0){ 
                return false;
            }
            boolean exists = false;
            Map<Integer, Integer> sumKeyValue = new HashMap<>();
            for (int i = 0; i < array.length; i++) { 
                Integer key = array[i];
                if(sumKeyValue.containsKey(s - key)){ 
                    System.out.println(key +" + "+ (s-key) +" = "+ s);
                    exists = true;
                }
                sumKeyValue.put(key, key);
            }
            return  exists;
        }

*  以上解法借助了HashMap，所以在时间复杂度计算中需要考虑containsKey的开销，如果出题人不让用jdk相关的集合类，我们可以通过数组自己实现一个Hash。

#### 更复杂的题型 ####

*  类似题：输入一个正数s，打印所有 和 为s的连续正数序列(至少含有2个数字)，例如，输入15，得到1+2+3+4+5 = 4+5+6=7+8，所以我们有打印出三个连续的序列1 ~ 5， 4 ~ 6， 7 ~ 8
 *  按如上题目的解决思路，此处也是寻找和为s的值，只不过是N数据的和，并且没有给出数字，那么案例中s=15，时候其实隐含的条件就是数组是 1~14 ，因为条件中都是正整数，那么有如下分析：
    
     *  依然双指针方法，因为此处我们需要找连续的数据，那么不能前后寻找，设positionBig = array.length，positionSmall = pogitionBig-1
     *  如果positionSmall ~ positionBig 中所有数据和 为 s，那么得出正解，此时让positionBig–，positionSmall = positionBig-1，继续求解
     *  如果positionSmall ~ positionBig中所有数据和 > s,那么说明数据和过大，我们应该减少大的值positionBig–
     *  如果positionSmall ~ positionBig 中所有数据和 < s, 说明数据和 过小，我们扩大数据的基数，让更多数据累加 positionSmall –
     *  我们从后向前逐个逐个的查询求和的组合，最后得到正解
     *  如下图所示：
 *  第一个数列：  
    ![在这里插入图片描述][2021070517414620.gif]
 *  第二个数列：  
    ![在这里插入图片描述][20210705174156675.gif]
 *  第三个数列：  
    ![在这里插入图片描述][20210705174205312.gif]
 *  经如上分析有如下代码：

/** * 在有序数组中查找和为 s的两个数字 * @author liaojiamin * @Date:Created in 17:38 2021/6/29 */
    public class FindSumInSortArray { 
    
        public static void main(String[] args) { 
            int[] arrayAll = new int[]{ 1,2,3,4,5,6,7,8,9,10,11,12,13,14};
            System.out.println(findAllSumList(arrayAll, 15));
        }
    
        public static boolean findAllSumList(int[] array, int s){ 
            if(array == null || array.length <= 0){ 
                return false;
            }
            boolean exists = false;
            int positionBig = array.length -1;
            int positionSmall = 0;
            while (array[positionBig] > s){ 
                positionBig --;
            }
            positionSmall = positionBig-1;
            while (positionBig > 0){ 
                Integer sum = 0;
                for (int i = positionSmall; i <= positionBig; i++) { 
                    sum+=array[i];
                }
                if(sum == s){ 
                    System.out.println(array[positionSmall] + " ~ "+ array[positionBig] +" = "+ s);
                    exists = true;
                    positionBig--;
                    positionSmall = positionBig-1;
                    continue;
                }
                if(sum < s){ 
                    positionSmall--;
                    if(positionSmall < 0){ 
                        return exists;
                    }
                    continue;
                }
                if(sum > s){ 
                    positionBig --;
                    continue;
                }
            }
            return exists;
        }
    }

*  如上实现代码中我用双指针的方式来做了一个类似双循环的操作，每次找到解，则递减一位，让标记为从一个方向遍历整个数组，时间复杂度O(n2)。

[上一篇：数据结构与算法–数组中出一次的数字][Link 1]  
[下一篇：数据结构与算法–翻转单词顺序][Link 2]

[20210705174112468.png]: /images/20221005/f4a0ec5b8d9349c79af3d08d7dc4d2d2.png
[2021070517414620.gif]: /images/20221005/d25d16a5524143879ca561806a662985.png
[20210705174156675.gif]: /images/20221005/c551cb9feacf4788a5484cc43fcaa31c.png
[20210705174205312.gif]: /images/20221005/c88a773be8234b3eb4b6411708796485.png
[Link 1]: https://blog.csdn.net/liaojiamin0102/article/details/118311083
[Link 2]: https://blog.csdn.net/liaojiamin0102/article/details/118406709