LeetCode: 1. Two Sum
Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.
Example: Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].
自己的答案，4ms，提交的错误次数太多：
public class Solution { public int[] twoSum(int[] nums, int target) { if (nums == null || nums.length == 0) { return new int[0]; } int length = nums.length; int max = nums[0]; int min = nums[0]; for (int i = 1; i < length; i++) { if (nums[i] > max) { max = nums[i]; } if (nums[i] < min) { min = nums[i]; } } int half = 2 * (Math.abs(max) + Math.abs(min)); int[] arrays = new int[2 * half + 1]; int[] result = new int[2]; int[] same = new int[2]; same[0] = -1; same[1] = -1; for (int i = 0; i < length; i++) { int left = nums[i] + half - min; int right = (target - nums[i]) + half - min; if (left != right) { arrays[left] = i + 1; } else { if (same[0] < 0) { same[0] = i; } else if (same[1] < 0) { same[1] = i; return same; } } if (right != left && arrays[right] > 0) { result[0] = arrays[right] - 1; result[1] = arrays[left] - 1; break; } } return result; } }最快的答案，3ms：
public class Solution { public int[] twoSum(int[] nums, int target) { short[] map = new short[20050]; int size = 50; for (int i = 0; i < nums.length; i++) { map[nums[i] + size] = (short) (i + 1); int diff = target - nums[i + 1] + size; if (diff < 0) continue; short d = map[diff]; if (d > 0) return new int[]{d - 1, i + 1}; } return null; } }简洁的答案：
public int[] twoSum(int[] numbers, int target) { int[] result = new int[2]; Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < numbers.length; i++) { if (map.containsKey(target - numbers[i])) { result[1] = i + 1; result[0] = map.get(target - numbers[i]); return result; } map.put(numbers[i], i + 1); } return result; }