漫画算法题:两数之和与三数之和

简介: 我们来举个例子,给定下面这样一个整型数组(假定数组不存在重复元素):我们随意选择一个特定值,比如13,要求找出两数之和等于13的全部组合。由于12+1 = 13,6+7 = 13,所以最终的输出结果(输出的是下标)如下:

640.png640.png640.png

 

 

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

640.png

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

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

1 6

2 7

640.png640.png

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

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

640.png

 

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

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

640.png


发现121相加的结果是13,符合要求。

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

 

640.png640.png640.png

 

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

640.png640.png640.png

640.png640.png640.png640.png

 

 

640.png640.png640.png640.png640.png640.png640.png640.png640.png640.png640.png640.png

 

让我们来具体演示一下:


 

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

640.png

 

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

640.png

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

 

640.png

 

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

640.png640.png640.png

public class FindSumNumbers {
    public static List<List<Integer>> twoSum(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        List<List<Integer>> 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<List<Integer>> resultList = twoSum(nums, 13);
        for(List<Integer> list : resultList){
            System.out.println(Arrays.toString(list.toArray()));
        }
    }
}

640.png640.png640.png

 public static List<List<Integer>> twoSumV2(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        List<List<Integer>> 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;
    }

640.png640.png640.png

 

 

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

 

640.png 

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

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

640.png

5 62

5 17

3 91

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

 

640.png

 

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

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

640.png

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

640.png

 

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

640.png

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

640.png

 

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

640.png


 public static List<List<Integer>> threeSum(int[] nums, int target) {
        List<List<Integer>> resultList = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            Map<Integer, Integer> 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;
    }

 

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

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

640.png640.png640.png640.png

 

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

 640.png

 640.png

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

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

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

640.png

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

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

640.png

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

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

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

因此我们成功找到了一组匹配的组合:139

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

 640.png

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

640.png

于是我们让指针j右移:

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

157

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

640.png

 

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

于是我们让指针j右移:

640.png

 

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

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

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

640.png

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

我们让指针k左移:

 640.png

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

我们让指针k继续左移:

 640.png

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

我们让指针j右移:

640.png

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

我们让指针k左移:

640.png 

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

256

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


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

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

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

640.png640.png

 public static List<List<Integer>> threeSumv2(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> resultList = new ArrayList<List<Integer>>();
        //大循环
        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<nums.length; j++) {
                // k指针向左移动
                while (j<k && (nums[j]+nums[k])>d) {
                    k--;
                }
                //双指针重合,跳出本次循环
                if (j == k) {
                    break;
                }
                if (nums[j] + nums[k] == d) {
                    List<Integer> list = Arrays.asList(nums[i], nums[j], nums[k]);
                    resultList.add(list);
                }
            }
        }
        return resultList;
    }

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



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

640.png

相关文章
|
8月前
|
算法
算法每日一题---两数之和
算法每日一题---两数之和
39 0
|
8月前
|
存储 算法 Python
python 算法 两数之和 的多种解法
python 算法 两数之和 的多种解法
|
缓存 算法 Java
【手绘算法】力扣 1 两数之和(Two Sum)
Hi,大家好,我是Tom。一个美术生转到Java开发的程序员。从今天开始,我将带大家每天刷一道题。我会用手绘的方式给大家讲解解题思路。在解题过程中,也会手写一些伪代码。当然,如果想要完整的源码的话,可以到我的个人主页简介中获取。 今天给大家分享的是力扣启蒙题第1题,求两数之和。虽然很简单,但是它的通过率只有52%。
105 0
|
5月前
|
存储 算法 Java
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
LeetCode初级算法题:两数之和+斐波拉契数列多种java解法
57 0
|
7月前
|
存储 算法 数据可视化
【漫画算法】哈希表:古代皇帝的秘密魔法书
【漫画算法】哈希表:古代皇帝的秘密魔法书
|
7月前
|
算法 搜索推荐 数据可视化
【漫画算法】插入排序:插入宝石的传说
【漫画算法】插入排序:插入宝石的传说
|
7月前
|
存储 算法 Java
【经典算法】LeetCode1:两数之和(Java/C/Python3实现含注释说明,Easy)
【经典算法】LeetCode1:两数之和(Java/C/Python3实现含注释说明,Easy)
40 1
|
7月前
|
算法 搜索推荐 数据可视化
【漫画算法】指挥官的排序战术:快速排序算法解密
【漫画算法】指挥官的排序战术:快速排序算法解密
|
8月前
|
存储 算法
Leetcode 30天高效刷数据结构和算法 Day1 两数之和 —— 无序数组
给定一个无序整数数组和目标值,找出数组中和为目标值的两个数的下标。要求不重复且可按任意顺序返回。示例:输入nums = [2,7,11,15], target = 9,输出[0,1]。暴力解法时间复杂度O(n²),优化解法利用哈希表实现,时间复杂度O(n)。
55 0
|
8月前
|
存储 算法
【优选算法专栏】专题九:链表--------两数之和
【优选算法专栏】专题九:链表--------两数之和
43 0