s1：twosum

    package problems.s1_TwoSum;

    import java.util.HashMap;

    public class TwoSum {

/**
 * Desc:
 * 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].
 */
public static void main(String[] args) {
    int[] arr = {0,3,4,0};
    System.out.println(twoSum(arr,6)[0]+":"+twoSum(arr,6)[1]);
}
/**
 * 第一种算法，循环遍历，时间复杂度为o(n^2)
 * @param nums
 * @param target
 * @return
 */
public static int[] twoSum(int[] nums, int target) {
    int[] answer = new int[2];
    for(int i=0,j=0;i<nums.length;i++){
         for(j=i+1;j<nums.length;j++){
            if(nums[i]+nums[j]==target){
                answer[0]=i;
                answer[1]=j;
                break;
            }
        }
    }
    return answer;
}
/**
 * 第二种算法，使用hashmap，时间复杂度降低为o(n)
 * @param nums
 * @param target
 * @return
 */
public static int[] twoSum2(int[] nums, int target) {
    int[] answer = new int[2];
    HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < nums.length; ++i){
        map.put(nums[i], i);
    }
    for (int i = 0; i < nums.length; ++i){
        int b = target - nums[i];
        if (map.containsKey(b) && i != map.get(b))
            answer = {i, map.get(b)};
     }
     return answer;
}

}