Leetcode 1: Two Sum 加和

PascalXie 发布于2019-08-14 17:01 / 1634人阅读

摘要：难度就是说给一个整数数组如给一个目标数字如从数组中找出相加为这个目标数字的两个数的下标就返回的下标只需要给出满足条件的一对数字即可这个题想起来比较直接此处给出两种解法这之后的题目中还有多个数字相加的相对较难的题目第一种将数组排序以两个游标

Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution.
Example: 
Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

难度: Easy.

就是说, 给一个整数数组(如[2, 7, 11, 15]), 给一个目标数字(如9), 从数组中找出相加为这个目标数字的两个数的下标. 2+7=9, 就返回2,7的下标[0,1]. 只需要给出满足条件的一对数字即可.

这个题想起来比较直接, 此处给出两种解法, 这之后的题目中, 还有多个数字相加的相对较难的题目.

第一种:
将数组排序, 以两个游标从两头向中间逼近

如果和偏大, 就把右游标向左挪动

如果和偏小, 就把左游标向右挪动

最终返回正确的下标. 此算法时间复杂度是 O(nlogn).

public class Solution {
    public int[] twoSum(int[] nums, int target) {

        class Pair {
            int idx;
            int val;
        }

        Pair[] pnums = new Pair[nums.length];
        for (int i = 0; i < nums.length; i++) {
            pnums[i] = new Pair();
            pnums[i].idx = i;
            pnums[i].val = nums[i];
        }

        Arrays.sort(pnums, new Comparator() {

            @Override
            public int compare(Pair o1, Pair o2) {
                if (o1.val > o2.val) {
                    return 1;
                } else if (o1.val < o2.val) {
                    return -1;
                } else {
                    return 0;
                }
            }

        });

        int lp = 0;
        int rp = nums.length - 1;
        while (true) {
            int sum = pnums[lp].val + pnums[rp].val;
            if (sum == target) {
                break;
            } else if (sum > target) {
                rp--;
            } else {
                lp++;
            }
        }
        if (pnums[lp].idx < pnums[rp].idx) {
            return new int[] { pnums[lp].idx, pnums[rp].idx };
        } else {
            return new int[] { pnums[rp].idx, pnums[lp].idx };
        }
    }

    public static void main(String[] args) {
        int[] a1 = { 3, 2, 4 };
        Solution s = new Solution();
        int[] ret = s.twoSum(a1, 6);
        System.out.println("" + ret[0] + " " + ret[1]);
    }
}

第二种:
使用一个map, 记录值->下标的映射关系(重复的值其实覆盖了没关系).
循环看每个值, 对于值a, 从map中查找(target-a), 如果存在, 则输出这两个数值的下标即可.

由于使用HashMap, 算法的时间复杂度是O(n)

public class Solution2 {
    public int[] twoSum(int[] nums, int target) {
        Map nmap = new HashMap();
        for (int i = 0; i < nums.length; i++) {
            nmap.put(nums[i], i);
        }

        int i = 0;
        int j = 0;
        for (; i < nums.length; i++) {
            if (nmap.containsKey(target - nums[i])) {
                j = nmap.get(target - nums[i]);
                if (i != j) {
                    break;
                }
            }
        }
        if (i < j) {
            return new int[] { i, j };
        } else {
            return new int[] { j, i };
        }

    }

    public static void main(String[] args) {
        int[] a1 = { 3, 2, 4 };
        Solution2 s = new Solution2();
        int[] ret = s.twoSum(a1, 6);
        System.out.println("" + ret[0] + " " + ret[1]);
    }
}

idc机房托管服务器托管 two-sum LeetCode two LeetCode_String

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/66378.html

leetcode 1 Two Sum Java & JavaScript解法

摘要：返回这两个元素的位置。每个输入都有且仅有一组满足条件的元素。想法如果使用蛮力法可以简单的解决这个问题。但是需要两层循环，效率低。用来存储，每一个元素和目标元素的差值和这个元素的位置。因为里的对象也是键值对。题目详情 Given an array of integers, return indices of the two numbers such that they add up t...

Guakin_Huang 2019-08-22 14:56 评论0 收藏0
leetcode 1 Two Sum Java & JavaScript解法

摘要：返回这两个元素的位置。每个输入都有且仅有一组满足条件的元素。想法如果使用蛮力法可以简单的解决这个问题。但是需要两层循环，效率低。用来存储，每一个元素和目标元素的差值和这个元素的位置。因为里的对象也是键值对。题目详情 Given an array of integers, return indices of the two numbers such that they add up t...

chanjarster 2019-08-15 14:26 评论0 收藏0
leetcode 416 Partition Equal Subset Sum

摘要：如果是奇数的话，那一定是不满足条件的，可以直接返回。如果是偶数，将除获得我们要求的一个子数组元素的和。如何暂存我们计算的中间结果呢声明一个长度为的布尔值数组。每个元素的布尔值代表着，数组中是否存在满足加和为的元素序列。题目详情 Given a non-empty array containing only positive integers, find if the array ca...

jsummer 2019-08-16 11:07 评论0 收藏0
leetcode 2 Add Two Numbers

摘要：我们的目的是求出两个数字的加和，并以同样的形式返回。假设每个都不会存在在首位的，除非数字本身就是想法这道题主要要求还是熟悉的操作。这道题由于数字反序，所以实际上从首位开始相加正好符合我们笔算的时候的顺序。题目详情 You are given two non-empty linked lists representing two non-negative integers. The d...

Integ 2019-08-15 14:19 评论0 收藏0
Two Sum系列 Leetcode解题记录

摘要：如果没有，就到里面复杂度分析就是，因为只扫了一遍数组。复杂度分析当然就是最坏情况了，也是标准的双指针复杂度。复杂度分析这种题应该不太需要分析复杂度吧，能实现就行。复杂度分析还是最后再说两句所以可以看出，很多题目思路一致，换汤不换药。 Two Sum 友情提示：篇幅较长，找题目的话，右边有目录，幸好我会MarkDown语法。改成了系列模式，因为类似的题不少，本质上都是换壳，所以在同一篇文...

andong777 2019-08-14 14:31 评论0 收藏0