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].

给出的类和方法参数

class Solution {
    public int[] twoSum(int[] nums, int target) {
            }
}

初步一看，简单

class Solution {

    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++)  {
                if (nums[i] + nums[j] == target) {
                    indexs[0] = i;
                    indexs[1] = j;
                }
            }
        }
        return indexs;
    }
}

提交之后，居然测试通过了，可见testcase不够严格，假如nums里没有任何两个数字和未target，那么if永远进不去，indexs引用的两个对象的值都是初值0，这显然与本意不符，因此需要加一个异常

class Solution {

    public int[] twoSum(int[] nums, int target) {
        int[] indexs = new int[2];
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++)  {
                if (nums[i] + nums[j] == target) {
                    indexs[0] = i;
                    indexs[1] = j;
                    return indexs;
                }
            }
        }
        throw new IllegalArgumentException("These 2 numbers not exist");
    }
}

题目已经说明只有一种解决方案，而且一个数字只能用一次，这么写应该OK

依次循环，用一个map，数组值为value，下表为key

package com.maoxiaomeng;

import java.util.HashMap;
import java.util.Map;

/**
 * @author lihui
 * @date 2018/3/26 12:31
 */

class Solution {
    public int[] twoSum(int[] nums, int target) {
        int len = nums.length;
        int temp[] = new int[2];
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        /**
         *  key =>  value
         *  2   =>  0
         *  7   =>  1
         *  11  =>  2
         *  15  =>  3
         */
        for (int i = 0; i < len; i++) {
            if (! map.containsKey(nums[i])) {
                map.put(nums[i], i);
            }
            if (map.containsKey(target - nums[i]) && i != map.get(target - nums[i])) {
                temp[0] = i;
                temp[1] = map.get(target - nums[i]);
                return temp;
            }
        }
        throw new IllegalArgumentException("not exist");
    }
}