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

• 解决

package com.lsy.leetcode;

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

public class TwoSum {
    
     public static int[] twoSum1(int[] nums, int target) {
            int size=nums.length;
            int[] solution=new int[2];
            for(int i=0;i<size;i++) {
                int exact=target-nums[i];
                for(int j=i+1;j<size;j++) {
                    if(nums[j]==exact) {
                        solution[0]=i;
                        solution[1]=j;
                        return solution;}
                }
            }
            
            return solution;
            
        }

     
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        int[] nums= {3,2,4};
        int target=6;
        System.out.println(Arrays.toString(twoSum1(nums,target)));
        //Arrays类得到了补充完整的Arrays.toString方法。专门为了将任何类型的数组转变为字符串而设计的。
        //数组直接tostring输出是地址
    }
//brute force:  %time o(n^2):最坏，n(n-1)/2   %space  o(1)最坏几个
    public int[] twoSum2(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {     //直接nums.length
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[j] == target - nums[i]) {
                    return new int[] { i, j };     //简洁，初始化  new int[]{i,j}
                }
            }
        }
        throw new IllegalArgumentException("No two sum solution"); //不输出就扔出异常
    }
//Two-pass Hash Table %time o(1):最坏n+n  系数不重要 2n=n  %space o(n)
    public int[] twoSum3(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();  //数据结构
        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);                    //key value的选择
        }
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (map.containsKey(complement) && map.get(complement) != i) {
                return new int[] { i, map.get(complement) };
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }



//One-pass Hash Table  %time o(n) %space o(n)
public int[] twoSum4(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {    //一个循环解决
        int complement = target - nums[i];
        if (map.containsKey(complement)) {      //肯定不包括自己   
            return new int[] { map.get(complement), i };
        }
        map.put(nums[i], i);
    }
    throw new IllegalArgumentException("No two sum solution");
}
}