Leetcode 1: Two Sum 加和

PascalXie 發布于2019-08-14 17:01 / 1778人閱讀

摘要：難度就是說給一個整數數組如給一個目標數字如從數組中找出相加為這個目標數字的兩個數的下標就返回的下標只需要給出滿足條件的一對數字即可這個題想起來比較直接此處給出兩種解法這之后的題目中還有多個數字相加的相對較難的題目第一種將數組排序以兩個游標

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]);
    }
}

云服務器 GPU云服務器 two-sum LeetCode two LeetCode_String

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/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