[LintCode/LeetCode] Two Sum

xiaoxiaozi 发布于2019-08-14 15:22 / 1019人阅读

摘要：就不说了，使用的解法思路如下建立，对应该元素的值与之差，对应该元素的。然后，循环，对每个元素计算该值与之差，放入里，。如果中包含等于该元素值的值，那么说明这个元素正是中包含的对应的差值。返回二元数组，即为两个所求加数的序列。

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就不说了，使用HashMap的解法思路如下：
建立HashMap，key对应该元素的值与target之差，value对应该元素的index。
然后，循环，对每个元素numbers[i]计算该值与target之差，放入map里，map.put(target-numbers[i], i)。
如果map中包含等于该元素值的key值，那么说明这个元素numbers[i]正是map中包含的key对应的差值diff(=target-numbers[map.get(numbers[i])])。那么，返回map中对应元素的index+1放入res[0]，然后将i+1放入res[1]。返回二元数组res，即为两个所求加数的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;
    }
}

云服务器 GPU云服务器 two-sum two sum two.js cdn

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

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

[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 2019-08-14 15:21 评论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 2019-08-16 12:37 评论0 收藏0
[LintCode/LeetCode] Trapping Rain Water [栈和双指针]

摘要：一种是利用去找同一层的两个边，不断累加寄存。双指针法的思想先找到左右两边的第一个峰值作为参照位，然后分别向后向前每一步增加该位与参照位在这一位的差值，加入，直到下一个峰值，再更新为新的参照位。 Problem Given n non-negative integers representing an elevation map where the width of each bar i...

bluesky 2019-08-14 15:19 评论0 收藏0
[LintCode/LeetCode] Merge Two Sorted Lists

摘要：先考虑和有无空集，有则返回另一个。新建链表，指针将和较小的放在链表顶端，然后向后遍历，直到或之一为空。再将非空的链表放在后面。 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 2019-08-14 15:22 评论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 2019-08-14 15:19 评论0 收藏0