剑指Offer（四十二）-- 双指针法求解和为S的两个数字

秦怀杂货店

发布于 2022-02-15 13:59:27

1.7K0

代码已经同步到刷题仓库：CodeSolution 仓库地址：https://github.com/Damaer/CodeSolution 文档地址：https://damaer.github.io/CodeSolution/ 如果有图片，图片都是draw.io绘制，在/drawio文件夹下。

题目描述

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

返回值描述:

对应每个测试案例，输出两个数，小的先输出。

输入

[1,2,4,7,11,15],15

返回值

[4,11]

双指针法

前面一篇讲解的是暴力破解和hash法，这里讲解的是双指针法。

由于数组nums[]是有序的，也就是第一个数字是最小的，第二个数字是最大的，那么我们使用一个指针i指向数组第一个元素，一个指针j指向数组最后一个元素。i指针往右边移动，j指针往左边移动,直到两者相撞（相等）。

如果nums[i]+nums[j]==sum,那么说明这个是可能存在的解，需要计算两者的乘积，如果比保存的乘积还小，则更新结果。同时左边指针i往右边移动一位，右边指针j往左边移动一位。
如果nums[i] + nums[j] > sum,则说明和太大了，比sum还要大，则右边的指针j需要左移一步，即是j--。
如果nums[i] + nums[j] < sum,则说明和太小了，比sum还要小，则左边的指针i需要左移一步，即是i++。

    public ArrayList<Integer> FindNumbersWithSum2(int[] array, int sum) {
        ArrayList<Integer> results = new ArrayList<>();
        long mutip = 999999999;
        if (array != null && array.length > 2) {
           int left = 0,right = array.length-1;
           while(left<right){
               if(array[left]+array[right]==sum){
                   if(array[left]*array[right]<mutip){
                       mutip = array[left]*array[right];
                       results.clear();
                       results.add(array[left]);
                       results.add(array[right]);
                   }
                   left++;
                   right--;
               }else if(array[left]+array[right]>sum){
                   right--;
               }else{
                   left++;
               }
           }
        }
        return results;
    }

由于左右指针加起来最多是将数组遍历一遍，所以时间复杂度为O(n)。

【作者简介】：秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。写好每一篇文章，期待和你们一起交流。

此文章仅代表自己（本菜鸟）学习积累记录，或者学习笔记，如有侵权，请联系作者核实删除。人无完人，文章也一样，文笔稚嫩，在下不才，勿喷，如果有错误之处，还望指出，感激不尽~

- END -

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2021-02-07，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法