文档章节

[leetcode] Two Sum

jdflyfly
 jdflyfly
发布于 2014/06/23 23:57
字数 343
阅读 816
收藏 0

https://oj.leetcode.com/problems/two-sum/

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.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2


思路1:对于每一个元素,遍历寻找另一个元素使得和为target,时间复杂度O(n^2)。

思路2:先排序,然后首尾两个指针向中间靠拢,两指针所指元素大于target,移动尾指针,小于target移动头指针,直至找到结果或者两个指针相遇。时间复杂度O(nlogn)。此方法可推广值3Sum,4Sum等,有待整理。

思路3:利用hashmap,将每个元素值作为key,数组索引作为value存入hashmap,然后遍历数组元素,在hashmap中寻找与之和为target的元素。 时间复杂度O(n),空间复杂度O(n)。


public class Solution {
	public int[] twoSum(int[] numbers, int target) {
		int len = numbers.length;
		int[] result = new int[2];
		Map<Integer, Integer> map = new HashMap<Integer, Integer>();
		for (int i = 0; i < len; i++) {
			map.put(numbers[i], i);
		}

		for (int i = 0; i < len; i++) {
			int one = numbers[i];
			Integer two = map.get(target - one);
			if (two != null && i < two) {
				result[0] = i + 1;
				result[1] = two + 1;
				break;
			}
		}
		return result;

	}
}



© 著作权归作者所有

jdflyfly
粉丝 5
博文 115
码字总数 30127
作品 0
杭州
程序员
私信 提问
leetcode题解(二叉树和递归问题)

这篇博客我们主要来看二叉树和二叉树问题中使用递归来解决问题的思路。这类问题有时思路很简单,这是因为二叉树具有天然的递归结构,所以我们使用递归的解法解决二叉树有关的问题就变得非常明...

吴小琪
2018/06/26
0
0
Leetcode_Problem 16_3 Sum Closest

题目 问题网址: https://leetcode.com/problems/3sum-closest/description/ 问题描述: Given an array S of n integers, find three integers in S such that the sum is closest to a giv......

quiet_girl
2018/03/09
0
0
LeetCode 64. Minimum Path Sum

原题 Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only mov......

dby_freedom
2018/10/11
0
0
[算法][LeetCode] Dynamic Programming(DP)动态规划

极值的问题一般考虑用DP [LeetCode] Coin Change 硬币找零 http://www.cnblogs.com/grandyang/p/5138186.html [LeetCode] Coin Change 2 硬币找零之二 http://www.cnblogs.com/grandyang/p/7......

素雷
2017/10/19
9
0
LeetCode日记2

LeetCode-5 思路: (1)最后用子字符串操作返回string。 return s.substr(startpos, maxlength); (2)回文串的判断: 1)首先找出回文串中间连续的重复的字符。 2)再向两边进行判断 (3...

fxdhdu
2015/10/19
72
0

没有更多内容

加载失败,请刷新页面

加载更多

Cantata 8.0有哪些新变化

Cantata 8.0 于2018年5月发布,这一重大版本的升级在以往技术的基础上增添了关键性新功能,并且对用户界面进行了全面改进,这个文档简要介绍了8.0中的主要变化。 Cantata 于2018年5月发布,本...

旋极科技
17分钟前
7
0
在线客服系统企业用的如何?

现在很多企业都在使用在线客服系统,但是销售订单没有显著增加这是为什么呢? 一:我们企业的客服人员是否有做好真正的接待工作? 是否每天都有对网站上的访客进行接待? 相关管理人员有没有做...

唯喏
26分钟前
5
0
Hystrix实现主线程和子线程的ThreadLocal上下文传递

问题描述 我在使用日志链路追踪的时候(基于SLF4J MDC机制实现日志的链路追踪),我发现使用Hystrix线程池隔离的时候,我不能将子线程没有复制主线程的MDC上下文(Slf4j MDC机制 ),导致日志链...

xiaolyuh
32分钟前
5
0
基于CentOS7搭建GitLab

基于CentOS7搭建GitLab 12018.11.02 16:38:51字数 959阅读 3790 本文作者:蓝雄威,叩丁狼高级讲师。原创文章,转载请注明出处。 一、简介 Git Lab GitLab是利用 Ruby on Rails 一个开源的版...

linjin200
33分钟前
3
0
AJAX技术

1.1 准备工作 因为AJAX也需要请求服务器,异步请求也是请求服务器,所以我们需要先写好服务器端代码,即编写一个Servlet! 这里,Servlet很简单,只需要输出“Hello AJAX!”。 public class...

Pak_key
34分钟前
4
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部