給定一個(gè)int數(shù)組攀例，其中兩個(gè)數(shù)相加等于一個(gè)特定值痰洒，返回這兩個(gè)數(shù)的索引
示例
int數(shù)組： [2, 7, 11, 15], 特定值 ： 9,
因?yàn)椋?nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
解決方案
package com.zss;
import java.util.HashMap;
import java.util.Map;
public class Solution {
public static void main(String[] args) {
int[] location = twosum2(new int[]{2, 8, 11, 7, 15}, 9);
for (int i = 0; i < location.length; i++) {
System.out.print(location[i]);
}
}
/**
* 空間復(fù)雜度O(1)
* 時(shí)間復(fù)雜度O(n*n)
*
* @param nums
* @param target
* @return
*/
public static int[] twosum(int[] nums, int target) {
int[] location = new int[]{0, 1};
for (int i = 0; i < nums.length; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] == target) {
location[0] = i;
location[1] = j;
}
}
}
return location;
}
/**
* 空間復(fù)雜度O(n)
* 時(shí)間復(fù)雜度O(n)
*
* @param nums
* @param target
* @return
*/
public static int[] twosum2(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for (int i = 0; i < nums.length; i++) {
if (map.containsKey(target - nums[i]) && map.get(target - nums[i]) != i) {
return new int[]{i, map.get(target - nums[i])};
}
}
throw new IllegalArgumentException("no solution");
}
/**
* 時(shí)間復(fù)雜度O(n)
* 空間復(fù)雜度O(n)
*
* @param nums
* @param target
* @return
*/
public static int[] twosum3(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[]{i, map.get(complement)};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No solution");
}
}
