import java.util.HashMap;

import java.util.Map;

public class TwoSum_1 {

/**

* 暴力解法：两次遍历数组查找相加等于目标值的两个元素

* 复杂度：O(n^2)

* @param nums

* @param target

* @return

*/

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

int[] result = new int[2];

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

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

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

result[0] = i;

result[1] = j;

return result;

}

}

}

return result;

}

/**

* HashMap解法：使用空间换时间

* 复杂度：O(n)

* @param nums

* @param target

* @return

*/

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

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

int[] result = new int[2];

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

if(map.containsKey(target - nums[i])) {

result[0] = map.get(target - nums[i]);

result[1] = i;

return result;

}

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

}

return result;

}

}