当前位置:首页 > 公众号精选 > 程序员小灰
[导读]前一段时间,分别讲解了两道leecode上的经典算法题,今天就把这两道题整合起来,并修改了其中的细节问题,感谢大家的指正。

前一段时间,小灰分别讲解了两道leecode上的经典算法题:


漫画:如何在数组中找到和为 “特定值” 的两个数?

漫画:如何在数组中找到和为 “特定值” 的三个数?


今天,小灰把这两道题整合起来,并修改了其中的细节问题,感谢大家的指正。



—————  第二天  —————



什么意思呢?我们来举个例子,给定下面这样一个整型数组(假定数组不存在重复元素):



我们随意选择一个特定值,比如13,要求找出两数之和等于13的全部组合。


由于12+1 = 13,6+7 = 13,所以最终的输出结果(输出的是下标)如下:


【1, 6】

【2, 7】


小灰想表达的思路,是直接遍历整个数组,每遍历到一个元素,就和其他元素相加,看看和是不是等于那个特定值。


第1轮,用元素5和其他元素相加:



没有找到符合要求的两个元素。


第2轮,用元素12和其他元素相加:



发现12和1相加的结果是13,符合要求。


按照这个思路,一直遍历完整个数组。




————————————












让我们来具体演示一下:


第1轮,访问元素5,计算出13-5=8。在哈希表中查找8,发现查不到:



第2轮,访问元素12,计算出13-12=1。在哈希表中查找1,查到了元素1的下标是6,所以元素12(下标是1)和元素1(下标是6)是一对结果:



第3轮,访问元素6,计算出13-6=7。在哈希表中查找7,查到了元素7的下标是7,所以元素6(下标是2)和元素7(下标是7)是一对结果:



按照这个思路,一直遍历完整个数组即可。


public class FindSumNumbers {

    public static List> twoSum(int[] nums, int target) {
        Map map = new HashMap<>();
        List> resultList = new ArrayList<>();
        for (int i = 1; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other) && map.get(other) != i) {
                resultList.add(Arrays.asList(i,map.get(other)));
                //为防止找到重复的元素对,匹配后从哈希表删除对应元素
                map.remove(nums[i]);
            }
        }
        return resultList;
    }

    public static void main(String[] args) {
        int[] nums = {5,12,6,3,9,2,1,7};
        List> resultList = twoSum(nums, 13);
        for(List list : resultList){
            System.out.println(Arrays.toString(list.toArray()));
        }
    }

}


    public static List> twoSumV2(int[] nums, int target) {
        Map map = new HashMap<>();
        List> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int other = target - nums[i];
            if (map.containsKey(other)) {
                resultList.add(Arrays.asList(map.get(other),i));
            }
            map.put(nums[i], i);
        }
        return resultList;
    }



举个例子,给定下面这样一个整型数组(假定数组不存在重复元素):



我们随意选择一个特定值,比如13,要求找出三数之和等于13的全部组合。


由于5+6+2=13, 5+1+7=13,3+9+1=13,所以最终的输出结果如下(直接输出元素值即可):


【5, 6,2】

【5, 1,7】

【3, 9,1】



小灰的思路,是把原本的“三数之和问题”,转化成求n次“两数之和问题”。



我们以上面这个数组为例,选择特定值13,演示一下小灰的具体思路:


第1轮,访问数组的第1个元素5,把问题转化成从后面元素中找出和为8(13-5)的两个数:


如何找出和为8的两个数呢?按照上一次所讲的,我们可以使用哈希表高效求解:


第2轮,访问数组的第2个元素12,把问题转化成从后面元素中找出和为1(13-12)的两个数:



第3轮,访问数组的第3个元素6,把问题转化成从后面元素中找出和为7(13-6)的两个数:



以此类推,一直遍历完整个数组,相当于求解了n次两数之和问题。


    public static List> threeSum(int[] nums, int target) {
        List> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            Map map = new HashMap<>();
            int d1 = target - nums[i];
            //寻找两数之和等于d1的组合
            for (int j = i+1; j < nums.length; j++) {
                int d2 = d1 - nums[j];
                if (map.containsKey(d2)) {
                    resultList.add(Arrays.asList(nums[i], d2, nums[j]));
                }
                map.put(nums[j], j);
            }
        }
        return resultList;
    }


在上面的代码中,每一轮解决“两数之和问题”的时间复杂度是O(n),一共迭代n轮,所以该解法总的时间复杂度是O(n²)


至于空间复杂度,同一个哈希表被反复构建,哈希表中最多有n-1个键值对,所以该解法的空间复杂度是O(n)



我们仍然以之前的数组为例,对数组进行升序排列:




这样说起来有些抽象,我们来具体演示一下:


第1轮,访问数组的第1个元素1,把问题转化成从后面元素中找出和为12(13-1)的两个数。


如何找出和为12的两个数呢?我们设置两个指针,指针j指向剩余元素中最左侧的元素2,指针k指向最右侧的元素12:


计算两指针对应元素之和,2+12 = 14 > 12,结果偏大了。


由于数组是按照升序排列,k左侧的元素一定小于k,因此我们把指针k左移一位:


计算两指针对应元素之和,2+9 = 11< 12,这次结果又偏小了。


j右侧的元素一定大于j,因此我们把指针j右移一位:


计算两指针对应元素之和,3+9 = 12,正好符合要求!


因此我们成功找到了一组匹配的组合:1,3,9


但这并不是结束,我们要继续寻找其他组合,让指针k继续左移:


 计算两指针对应元素之和,3+7 = 10< 12,结果偏小了。


于是我们让指针j右移:


计算两指针对应元素之和,5+7 = 12,又找到符合要求的一组:


1,5,7


我们继续寻找,让指针k左移:


 计算两指针对应元素之和,5+6 = 11< 12,结果偏小了。


于是我们让指针j右移:


此时双指针重合在了一起,如果再继续移动,就有可能和之前找到的组合重复,因此我们直接结束本轮循环。


第2轮,访问数组的第2个元素2,把问题转化成从后面元素中找出和为11(13-2)的两个数。


我们仍然设置两个指针,指针j指向剩余元素中最左侧的元素3,指针k指向最右侧的元素12:


 计算两指针对应元素之和,3+12 = 15 > 11,结果偏大了。


我们让指针k左移:


 计算两指针对应元素之和,3+9 = 12 > 11,结果仍然偏大。


我们让指针k继续左移:


 计算两指针对应元素之和,3+7 = 10 < 11,结果偏小了。


我们让指针j右移:


 计算两指针对应元素之和,5+7 = 12 > 11,结果又偏大了。


我们让指针k左移:


 计算两指针对应元素之和,5+6 = 11,于是我们又找到符合要求的一组:


2,5,6


我们继续寻找,让指针k左移:


此时双指针又一次重合在一起,我们结束本轮循环。


按照这个思路,我们一直遍历完整个数组。


像这样利用两个指针指向数组两端,不断向中间靠拢调整来寻找匹配组合的方法,就是双指针法,也被称为“夹逼法”。


    public static List> threeSumv2(int[] nums, int target) {
        Arrays.sort(nums);
        List> resultList = new ArrayList>();
        //大循环
        for (int i = 0; i < nums.length; i++) {
            int d = target - nums[i];
            // j和k双指针循环定位,j在左端,k在右端
            for (int j=i+1,k=nums.length-1; j                // k指针向左移动
                while (jd) {
                    k--;
                }
                //双指针重合,跳出本次循环
                if (j == k) {
                    break;
                }
                if (nums[j] + nums[k] == d) {
                    List list = Arrays.asList(nums[i], nums[j], nums[k]);
                    resultList.add(list);
                }
            }
        }
        return resultList;
    }


上面这段代码表面上有三层循环,但每一轮指针j和k的移动次数加起来最多n-1次,因此该解法的整体时间复杂度是O(n²)


最关键的是,该解法并没有使用额外的集合(排序是直接在输入数组上进行的),所以空间复杂度只有O(1)


—————END—————



喜欢本文的朋友,欢迎关注公众号 程序员小灰,收看更多精彩内容

      
点个[在看],是对小灰最大的支持!


免责声明:本文内容由21ic获得授权后发布,版权归原作者所有,本平台仅提供信息存储服务。文章仅代表作者个人观点,不代表本平台立场,如有问题,请联系我们,谢谢!

本站声明: 本文章由作者或相关机构授权发布,目的在于传递更多信息,并不代表本站赞同其观点,本站亦不保证或承诺内容真实性等。需要转载请联系该专栏作者,如若文章内容侵犯您的权益,请及时联系本站删除。
换一批
延伸阅读

NVIDIA 量子模拟平台将通过各大云提供商提供,帮助科学家推进量子计算和算法研究

关键字: 量子计算 算法 量子云

随着科技的飞速发展,人工智能(AI)已经成为当今科技研究的热点和前沿。AI的快速发展不仅带来了许多新的应用场景和商业模式,也在推动科技进步的同时,引发了一系列关于其未来发展方向和潜在影响的深入讨论。本文将对人工智能的科技...

关键字: 人工智能 AI技术 算法

机器学习算法:机器学习是一种让计算机通过学习数据和模式来改进自身算法的技术。这些算法包括监督学习、无监督学习和强化学习。

关键字: 人工智能 机器学习 算法

随着信息技术的快速发展,机器学习作为人工智能的核心技术之一,正逐渐渗透到各个领域,引领着一场前所未有的科技变革。在机器学习的实际应用中,有三大重点至关重要,它们分别是数据质量、算法选择与模型评估。本文将深入探讨这三大重点...

关键字: 机器学习 数据质量 算法

在人工智能的浪潮中,机器学习已逐渐成为推动科技进步的核心动力。机器学习技术的广泛应用,从图像识别到自然语言处理,从智能推荐到自动驾驶,都离不开其三个基本要素:数据、算法和模型。本文将深入探讨这三个基本要素在机器学习中的作...

关键字: 机器学习 算法 人工智能

随着信息技术的迅猛发展,机器学习作为人工智能的核心技术之一,已经深入到了各个领域,为我们的生活和工作带来了翻天覆地的变化。无论是智能语音助手、自动驾驶汽车,还是个性化推荐、疾病预测,这些令人惊叹的应用背后,都离不开机器学...

关键字: 机器学习 人工智能 算法

机器学习的方法是指利用统计学方法和算法让计算机自动学习模式和规律,并通过数据进行预测和决策的一门学科。机器学习的主要目标是让计算机能够从数据中自我学习,通过训练模型来提高自身的性能。机器学习的方法可以从高层次上分为监督学...

关键字: 机器学习 算法

机器学习算法可以分为有监督学习、无监督学习、深度学习和强化学习等几种类型。每种类型都有其独特的优点和缺点。

关键字: 机器学习 算法

机器学习算法是指从大量历史数据中挖掘出其中隐含的规律,并用于回归(预测)或者分类的算法。机器学习是一种实现人工智能的方法,它使用模型来进行预测和推断。模型通过学习大量数据中的模式来提高预测准确性和分类准确性。机器学习算法...

关键字: 机器学习 算法

人工智能(AI)作为当今科技领域的核心驱动力,已经引起了全球范围内的广泛关注。随着算法的突破、数据量的增长以及计算能力的提升,AI技术正在以前所未有的速度发展。本文将深入探讨人工智能目前的发展现状,包括主要的技术进展、应...

关键字: 人工智能 算法 应用领域
关闭
关闭