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.
https://leetcode.com/problems/two-sum/
最直接的解法--上榔头... 时间复杂度 O(N^2), 空间复杂度 O(1)
1 public class Solution { 2 public int[] twoSum(int[] nums, int target) { 3 for (int i = 0; i < nums.length - 1; i ++) { 4 for (int j = i + 1; j < nums.length; j ++) { 5 if (nums[i] + nums[j] == target) { 6 return new int[]{i + 1, j + 1}; 7 } 8 } 9 } 10 return new int[2]; 11 } 12 }
进一步思考, 由于是两个值, 拿到任意一个值都可以通过目标值算出对应的配对数值来, 所以 -- HashMap 可以帮忙快速解决这个问题, 时间复杂度 O(N), 空间复杂度 O(N).
1 public class Solution { 2 HashMap<Integer, Integer> map = new HashMap<>(); 3 public int[] twoSum(int[] nums, int target) { 4 for (int i = 0; i < nums.length; i ++) { 5 if (map.containsKey(target - nums[i])) { 6 return new int[]{map.get(target - nums[i]) + 1, i + 1}; 7 } else { 8 map.put(nums[i], i); 9 } 10 } 11 12 return new int[2]; 13 } 14 }
原文：http://www.cnblogs.com/dbalgorithm/p/5161991.html