1. Two Sum

王朝学院·作者佚名  2016-05-28
窄屏简体版  字體: 小  |  中  |  大  |  超大  

1. 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=9Output:index1=1, index2=2

链接:http://leetcode.com/PRoblems/two-sum/

题解:

使用HashMap,一次遍历数组,Time Complexity - O(n),Space Complexity - O(n)

public class Solution { public int[] twoSum(int[] numbers, int target) { int result[] = {-1, -1}; if(numbers == null || numbers.length == 0) return result; HashMap<Integer, Integer> map = new HashMap<Integer, Integer>(); for(int i = 0; i < numbers.length; i++){ if(!map.containsKey(target - numbers[i])) map.put(numbers[i], i); else{ result[0] = map.get(target - numbers[i]) + 1; result[1] = i + 1; break; } } return result; }}

Reference:

http://www.cnblogs.com/springfor/p/3859618.html

 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
© 2005- 王朝網路 版權所有 導航