成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

[LintCode/LeetCode] Two Sum

xiaoxiaozi / 1080人閱讀

摘要：就不說(shuō)了，使用的解法思路如下建立，對(duì)應(yīng)該元素的值與之差，對(duì)應(yīng)該元素的。然后，循環(huán)，對(duì)每個(gè)元素計(jì)算該值與之差，放入里，。如果中包含等于該元素值的值，那么說(shuō)明這個(gè)元素正是中包含的對(duì)應(yīng)的差值。返回二元數(shù)組，即為兩個(gè)所求加數(shù)的序列。

Problem

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.

Notice

You may assume that each input would have exactly one solution

Example 
numbers=[2, 7, 11, 15], target=9
return [1, 2]
Challenge

Either of the following solutions are acceptable:

O(n) Space, O(nlogn) Time
O(n) Space, O(n) Time

Note

Brute Force就不說(shuō)了，使用HashMap的解法思路如下：
建立HashMap，key對(duì)應(yīng)該元素的值與target之差，value對(duì)應(yīng)該元素的index。
然后，循環(huán)，對(duì)每個(gè)元素numbers[i]計(jì)算該值與target之差，放入map里，map.put(target-numbers[i], i)。
如果map中包含等于該元素值的key值，那么說(shuō)明這個(gè)元素numbers[i]正是map中包含的key對(duì)應(yīng)的差值diff(=target-numbers[map.get(numbers[i])])。那么，返回map中對(duì)應(yīng)元素的index+1放入res[0]，然后將i+1放入res[1]。返回二元數(shù)組res，即為兩個(gè)所求加數(shù)的index序列。

Solution 
public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] res = new int[2];
        Map map = new HashMap();
        for (int i = 0; i < numbers.length; i++) {
            int diff = target-numbers[i];
            if (map.containsKey(numbers[i])) {
                res[0] = map.get(numbers[i])+1;
                res[1] = i+1;
            }
            map.put(diff, i);
        }
        return res;
    }
}

Brute Force

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int n = numbers.length;
        int[] res = new int[2];
        for (int i = 0; i < n; i++) {
            for (int j = i+1; j < n; j++) {
                if (numbers[i] + numbers[j] == target) {
                    res[0] = i+1;
                    res[1] = j+1;
                }
            }
        }
        return res;
    }
}

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://m.hztianpu.com/yun/65700.html

相關(guān)文章

  • [LintCode/LeetCode] Add Two Numbers

    Problem You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1s digit is at the head of the list. Write a f...

    hedzr 評(píng)論0 收藏0

  • [LintCode/LeetCode] Check Sum of K Primes

    Problem Given two numbers n and k. We need to find out if n can be written as sum of k prime numbers. Example Given n = 10, k = 2Return true // 10 = 5 + 5 Given n = 2, k = 2Return false Solution pub...

    lakeside 評(píng)論0 收藏0

  • [LintCode/LeetCode] Trapping Rain Water [棧和雙指針]

    摘要：一種是利用去找同一層的兩個(gè)邊，不斷累加寄存。雙指針?lè)ǖ乃枷胂日业阶笥覂蛇叺牡谝粋€(gè)峰值作為參照位，然后分別向后向前每一步增加該位與參照位在這一位的差值，加入，直到下一個(gè)峰值，再更新為新的參照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

    bluesky 評(píng)論0 收藏0

  • [LintCode/LeetCode] Merge Two Sorted Lists

    摘要：先考慮和有無(wú)空集，有則返回另一個(gè)。新建鏈表，指針將和較小的放在鏈表頂端，然后向后遍歷，直到或之一為空。再將非空的鏈表放在后面。 Problem Merge two sorted (ascending) linked lists and return it as a new sorted list. The new sorted list should be made by splici...

    dockerclub 評(píng)論0 收藏0

  • [LintCode/LeetCode] Intersection of Two Linked Lis

    Problem Write a program to find the node at which the intersection of two singly linked lists begins. Example The following two linked lists: A: a1 → a2 ↘ ...

    OldPanda 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

閱讀需要支付1元查看
<