import java.util.*;

/*

* @lc app=leetcode.cn id=1 lang=java

*

* [1] 两数之和

*/

class LeetCode_01_038 {

public int[] twoSum(int[] nums, int target) {

// hashmap, 时间 O(n),空间 O(n)

Map<Integer, Integer> numDic = new HashMap<Integer, Integer>();

// push and process

for (int i = 0; i < nums.length; ++i) {

if (numDic.containsKey(target - nums[i])

&& numDic.get(target - nums[i]) != i) {

return new int[]{numDic.get(target - nums[i]), i};

}

numDic.put(nums[i], i);

}

throw new IllegalArgumentException("No two sum solution");

}

public int[] twoSum1(int[] nums, int target) {

// hashmap, 时间 O(2n),空间 O(n)

Map<Integer, Integer> numDic = new HashMap<Integer, Integer>();

// push

for (int i = 0; i < nums.length; ++i) {

numDic.put(nums[i], i);

}

for (int i = 0; i < nums.length; ++i) {

if (numDic.containsKey(target - nums[i])

&& numDic.get(target - nums[i]) != i) {

return new int[]{i, numDic.get(target - nums[i])};

}

}

throw new IllegalArgumentException("No two sum solution");

}

public int[] twoSum2(int[] nums, int target) {

// check valid

// 暴力，时间 O(n^2)，空间 O(1)

for (int i = 0; i < nums.length - 1; ++i) {

for (int j = i + 1; j < nums.length; ++j) {

if (nums[i] + nums[j] == target) {

return new int[]{i, j};

}

}

}

throw new IllegalArgumentException("No two sum solution");

}

public static void main(String[] args) {

LeetCode_01_038 testCode_01_038 = new LeetCode_01_038();

int[] nums = new int[]{-1};

int[] result = testCode_01_038.twoSum2(nums, 3);

for (int i = 0; i < result.length; ++i) {

System.out.print(result[i] + ",");

}

}

}