美文网首页
LeetCode_0001_两数之和

LeetCode_0001_两数之和

作者: JayDroid | 来源:发表于2019-12-26 11:35 被阅读0次
    晓之以理动之以码.png

    一，题目

    给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
    你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
    示例:

    给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

    来源：力扣（LeetCode）
    链接：https://leetcode-cn.com/problems/two-sum
    著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

    二，题解

    1，方案分析

    • 方案1：两次遍历暴力破解

      • ①遍历array找到num1
      • ②再次遍历array,根据条件num1+num2=target 找到num2
      • ③返回两数的下标
      • 复杂度分析：Time:O(n^2) Space:O(1)

    • 方案2：两遍哈希表

      • ①遍历array，将每个元素以<num,index>形式存储到HashMap中
      • ②再次遍历array，根据条件num1+num2=target 从map中找到num2
      • ③返回两数的下标
      • 复杂度分析：Time:O(n) Space:O(n)

    • 方案3：一遍哈希表

      • ①遍历array，根据条件num1+num2=target 从map中寻找num2
      • ②返回两数的下标
      • ③将每个元素以<num,index>形式存储到HashMap中
      • 复杂度分析：Time:O(n) Space:O(n)

    • 方案4：指针法（已排序array）

      • ①声明两个指针 left right 分别指向数组开始和末尾
      • ②如果左右指针在数组下标取值范围内就进入循环
      • ③根据num1+num2=target移动指针，直到找到
      • ④返回 left right的值
      • 复杂度分析：Time:O(n) Space:O(1)

    2，代码实现

    完整代码：Github

    方案1：暴力法

    测试代码：

        /**
     * Solution1: 暴力法
     * 暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target - x 相等的目标元素。
     *
     * <p>
     * 复杂度分析：
     * 时间复杂度：O(n^2)
     * 对于每个元素，都需要通过遍历数组的其余元素进行计算来寻找目标元素，这将耗费 O(n) 的时间。
     * 因此总的时间复杂度为 O(n^2)。
     *
     * 空间复杂度：O(1)
     * 未使用其它额外的变量存储
     *
     * 实际测试值：
     * 本环境测试：数组长度5：1000 ，数组长度5万：5 079 573
     * LeetCode：时间 22 ms    内存 36.5 MB
     */
    private static void solution1() {
        System.out.println("-----Solution1-----\n");
        //测试数据
        //随机数组
        int[] numArray = getNumArray();
        //获取随机下标
        int[] targetIndex = getTargetIndexFromArray(numArray);
        //生成target
        int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
        System.out.println("target:\n" + target);

        //暴力法测试
        //开始时间纳秒
        long sTime = System.nanoTime();
        //暴力法题解算法
        int[] resultIndex = new Solution().twoSum1(numArray, target);
        //结束时间纳秒
        long eTime = System.nanoTime();
        System.out.println("nanoTime:\n" + (eTime - sTime));

        printArray("resultIndex:", resultIndex);

    }

    /**
     * @param numArray 给定一个整数数组
     * @param target   给定一个目标值
     * @return 和为目标值的那两个整数的下标
     */
    public int[] twoSum1(int[] numArray, int target) {
        //条件检查
        if (numArray == null || numArray.length < 2) {
            return new int[2];
        }
        //数组中的每个元素和其它所有元素都计算一遍
        for (int i = 0; i < numArray.length; i++) {
            //j 从i+1开始可以减少不必要的时间复杂度，也避免重复
            for (int j = i + 1; j < numArray.length; j++) {
                //如果找到了和为目标值的那两个整数
                if (numArray[i] + numArray[j] == target) {
                    return new int[]{i, j};
                }
            }
        }
        //其它情况
        throw new IllegalArgumentException("No two sum solution");
    }

    运行结果：

    -----Solution1-----

numArray:
39, 74, 13, 57, 60
target:
70
nanoTime:
11725
resultIndex:
2, 3

    -----Solution1-----

numArray:
5万条数据（请自行测试）
target:
1158586
nanoTime:
4 292 020
resultIndex:
20, 6461

    方案2：两遍哈希表

    测试代码：

        /**
     * Solution2: 两遍哈希表
     * <p>
     * 为了对运行时间复杂度进行优化，我们需要一种更有效的方法来检查数组中是否存在目标元素。如果存在，我们需要找出它的索引。
     * 保持数组中的每个元素与其索引相互对应的最好方法是什么？哈希表。
     *
     * <p>通过以空间换取速度的方式，我们可以将查找时间从 O(n) 降低到 O(1)。哈希表正是为此目的而构建的，
     * 它支持以 近似恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)。
     * 但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)。
     *
     * <p>一个简单的实现使用了两次迭代。
     * 在第一次迭代中，我们将每个元素的值和它的索引添加到表中。
     * 在第二次迭代中，我们将检查每个元素所对应的目标元素（target -nums[i]）是否存在于表中。
     * 注意，该目标元素不能是 nums[i]本身！
     *
     * 复杂度分析：
     * 时间复杂度：O(n)
     * 我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为O(n)。
     * 空间复杂度：O(n)
     * 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n个元素
     *
     * 实际测试值：
     * 本环境测试：数组长度5：60000 ，数组长度5万：1 369 711
     * LeetCode：时间 4 ms 内存 36.6 MB
     *
     */
    private static void solution2() {
        System.out.println("-----Solution2-----\n");
        //测试数据
        //随机数组
        int[] numArray = getNumArray();
        //获取随机下标
        int[] targetIndex = getTargetIndexFromArray(numArray);
        //生成target
        int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
        System.out.println("target:\n" + target);

        //开始时间
        long sTime = System.nanoTime();
        //两遍哈希表题解算法
        int[] resultIndex = new Solution().twoSum2(numArray, target);
        //结束时间
        long eTime = System.nanoTime();
        System.out.println("nanoTime:\n" + (eTime - sTime));

        printArray("resultIndex:", resultIndex);

    }

    /**
     * @param numArray 给定一个整数数组
     * @param target   给定一个目标值
     * @return 和为目标值的那两个整数的下标
     */
    public int[] twoSum2(int[] numArray, int target) {
        // 条件检查
        if (numArray == null || numArray.length < 2) {
            return new int[2];
        }
        //初始化一个HashMap
        Map<Integer, Integer> numMap = new HashMap<>();
        //将数组中<元素,下标> 转化为Map中的<key,value>
        for (int i = 0; i < numArray.length; i++) {
            numMap.put(numArray[i], i);
        }
        //遍历整个数组，找到每个元素
        for (int firstIndex = 0; firstIndex < numArray.length; firstIndex++) {
//            //方式一 secondIndex
//            //根据两数之和为target尝试获取secondIndex
//            Integer secondIndex = numMap.get(target - numArray[firstIndex]);
//            //如果找到了secondIndex并且secondIndex != firstIndex
//            if (secondIndex != null && secondIndex != firstIndex) {
//                return new int[]{firstIndex, secondIndex};
//            }

            //方式二 secondNum
            //根据两数之和为target获取 secondNum
            int secondNum = target - numArray[firstIndex];
            //如果map中包含secondNum并且 secondNum != firstNum
            if (numMap.containsKey(secondNum) && numMap.get(secondNum) != firstIndex) {
                return new int[]{firstIndex, numMap.get(secondNum)};
            }

        }

        //其它情况
        throw new IllegalArgumentException("No two sum solution");
    }

    运行结果：

    -----Solution2-----

numArray:
30, 28, 92, 60, 29
target:
152
nanoTime:
90198
resultIndex:
2, 3

    -----Solution2-----

numArray:
5万条数据（请自行测试）
target:
1477048
nanoTime:
15 190 543
resultIndex:
7, 46604

    方案3：一遍哈希表

    测试代码：

     /**
     * Solution3: 一遍哈希表
     * 事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，
     * 我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。
     * 如果它存在，那我们已经找到了对应解，并立即将其返回。
     *
     * 复杂度分析：
     * 时间复杂度：O(n)
     * 我们只遍历了包含有 nn 个元素的列表一次。在表中进行的每次查找只花费 O(1)O(1) 的时间
     * 空间复杂度：O(n)
     * 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n个元素
     *
     * 实际测试值：
     * 本环境测试：数组长度5：50000 ，数组长度5万：1 307 594
     * LeetCode：时间 3 ms 内存 37.8 MB
     */
    private static void solution3() {
        System.out.println("-----Solution3-----\n\n");
        //测试数据
        //随机数组
        int[] numArray = getNumArray();
        //获取随机下标
        int[] targetIndex = getTargetIndexFromArray(numArray);
        //生成target
        int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
//        int target = 6;
        System.out.println("target:\n" + target);

        //开始时间
        long sTime = System.nanoTime();
        //一遍哈希表题解算法
        int[] resultIndex = new Solution().twoSum3(numArray, target);
        //结束时间
        long eTime = System.nanoTime();
        System.out.println("nanoTime:\n" + (eTime - sTime));

        printArray("resultIndex:", resultIndex);

    }

    /**
     * @param numArray 给定一个整数数组
     * @param target   给定一个目标值
     * @return 和为目标值的那两个整数的下标
     */
    public int[] twoSum3(int[] numArray, int target) {
        // 条件检查
        if (numArray == null || numArray.length < 2) {
            return new int[2];
        }
        //初始化一个HashMap
        Map<Integer, Integer> numMap = new HashMap<>();
        //将数组中<元素,下标> 转化为Map中的<key,value>
        for (int firstIndex = 0; firstIndex < numArray.length; firstIndex++) {
            //方式一 secondIndex
//            //根据两数之和为target尝试获取secondIndex
//            Integer secondIndex = numMap.get(target - numArray[firstIndex]);
//            //如果找到了secondIndex 此时的secondIndex肯定不会和firstIndex相等的
//            if (secondIndex != null) {
//                return new int[]{firstIndex, secondIndex};
//            }

            //方式二 secondNum
            //根据两数之和为target获取 secondNum
            int secondNum = target - numArray[firstIndex];
            //如果map中包含secondNum
            if (numMap.containsKey(secondNum) && numMap.get(secondNum) != firstIndex) {
                return new int[]{firstIndex, numMap.get(secondNum)};
            }

            numMap.put(numArray[firstIndex], firstIndex);

        }

        //其它情况
        throw new IllegalArgumentException("No two sum solution");
    }

    运行结果：

    -----Solution3-----


numArray:
48, 26, 13, 29, 92
target:
42
nanoTime:
72273
resultIndex:
3, 2

    -----Solution3-----

numArray:
5万条数据（请自行测试）
target:
1439732
nanoTime:
1 179 748
resultIndex:
719, 250

    方案4：指针法（已排序array）

    测试代码：

    /**
     * Solution4: 排序+指针 （该方案不能通过LeetCode，下标错乱）
     * 如果给定的数据是已经排序的,我们可以通过移动指针来寻找和为目标值的那两个元素，使用指针可以避免使用额外的内存开销
     * <p>
     * 复杂度分析：
     * 时间复杂度：O(n)
     * 最坏的情况我们的while循环会遍历所有，所以时间复杂度为O(n)
     * 空间复杂度：O(1)
     * 所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n个元素
     * <p>
     * 实际测试值：
     * 本环境测试：数组长度5：10535 ，数组长度5万：47 321
     */
    private static void solution4() {
        System.out.println("-----Solution4-----\n\n");
        //测试数据
        //随机数组
        int[] numArray = getNumArray();
        //获取随机下标
        int[] targetIndex = getTargetIndexFromArray(numArray);
        //生成target
        int target = numArray[targetIndex[0]] + numArray[targetIndex[1]];
//        int target = 6;
        System.out.println("target:\n" + target);

        //对数组排序
        Arrays.sort(numArray);
        printArray("sorted numArray:", numArray);

        //开始时间
        long sTime = System.nanoTime();
        //排序+指针题解算法
        int[] resultIndex = new Solution().twoSum4(numArray, target);
        //结束时间
        long eTime = System.nanoTime();
        System.out.println("nanoTime:\n" + (eTime - sTime));

        printArray("resultIndex:", resultIndex);

    }

    /**
     * @param numArray 给定一个整数数组
     * @param target   给定一个目标值
     * @return 和为目标值的那两个整数的下标
     */
    public int[] twoSum4(int[] numArray, int target) {
        // 条件检查
        if (numArray == null || numArray.length < 2) {
            return new int[2];
        }

        //左指针初始指向第一个元素
        int left = 0;
        //右指针初始指向最后一个元素
        int right = numArray.length - 1;
        //如果左右指针在数组下标取值范围内就进入循环
        while ((left > -1 && left < numArray.length) && (right > -1 && right < numArray.length)) {
            //计算当前左右指针所指向的元素的和
            int tempTarget = numArray[left] + numArray[right];
            //当前得到的tempTarget小于target，右指针是最大了，所以需要将左指针向右增大移动
            if (tempTarget < target) {
                left++;
            }
            //当前得到的tempTarget大于target，左指针是最小了，所以需要将右指针向左减小移动
            else if (tempTarget > target) {
                right--;
            }
            //tempTarget等于target，找到了目标值
            else {
                return new int[]{left, right};
            }

        }

        //其它情况
        throw new IllegalArgumentException("No two sum solution");
    }

    运行结果：

    -----Solution4-----


numArray:
11, 86, 64, 75, 68
target:
150
sorted numArray:
11, 64, 68, 75, 86
nanoTime:
9675
resultIndex:
1, 4

    -----Solution3-----

numArray:
5万条数据（请自行测试）
target:
680708
nanoTime:
580 795
resultIndex:
17, 33852

    相关文章

      网友评论

          本文标题：LeetCode_0001_两数之和

          本文链接：https://www.haomeiwen.com/subject/zeukoctx.html

          延伸阅读

          深度阅读

          • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

          栏目导航

          热点阅读

          关于我们|服务条款|联系我们|LeetCode_0001_两数之和|投稿指南|网站地图|RSS订阅|排版工具|手机版

          提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

          Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

          备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

          本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

          所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！