算法之two sum

leetcode : two sum

题目：求给定数据中的两个值相加等于给定值，并返回这两个数据在数据中的下标。

例如：数组[2, 7, 5 , 9 , 11]，给定值为9。数组中2+7=9，返回其下标[0,1]

分析：求x+y=9，外层循环取出每个数x， 再内层循环取出y，如果x+y=9，则找到x,y

方案一：暴力法，嵌套遍历，时间复杂度O(N^2)

public static int[] twoSum(int[] nums, int target) {
 for (int i = 0; i < nums.length - 1; i++) {
 for (int j = i+1; j < nums.length; j++) { //注意内嵌从i+1开始到 length
 if (nums[i] + nums[j] == target) {
 return new int[]{i, j};
 }
 }
 }
 return null;
}

方案二：

• X+Y=9，转换一下就是 X = 9 - Y，也就是在数组中找出X的位置。时间复杂度为O(n)
• 利用Map,Set来解决。时间复杂度为O(1)
• O(1) + O(N) = O(N)

public static int[] twoSum1(int[] nums, int target) {
 Map<integer> numsMap = new HashMap();
 for(int i = 0; i < nums.length; i++) {
 numsMap.put(nums[i], i);
 }
 for(int i = 0; i < nums.length; i++) {
 int k = target - nums[i];
 if(numsMap.containsKey(k) && numsMap.get(k) != i) {
 return new int[]{i, numsMap.get(k)};
 }
 }
 return null;
}
/<integer>

方法三：一遍哈希法

• 时间复杂度：O(N)
• 空间复杂度：O(N)

private int[] findIndex3(int[] nums, int target) {
 Map<integer> map = new HashMap();
 for(int i = 0; i < nums.length; i++) {
 int temp = target - nums[i];
 if(map.containsKey(temp) && map.get(temp) != i) {
 return new int[] {i, map.get(temp)};
 }
 map.put(nums[i], i);
 }
 throw new IllegalArgumentException("no two sum solution!");
}
/<integer>