-
hadoop迷
暴力法:
public class Solution { public static int[] twoSum(int[] nums, int target) { int[] result = new int[2]; for (int i = 0; i < nums.length; i++) { for (int j = 0; j < nums.length; j++) { if (i!=j&&nums[i] + nums[j] == target) { result[0] = i; result[1] = j; return result; } } } return null; } public static void main(String[] args) { int[] nums = new int[]{2, 7, 11, 15}; int target = 9; int[] result = twoSum(nums, target); System.out.println("[" + result[0] + "," + result[1] + "]"); } }
-
Tony
先排序,后一次遍历,时间复杂度O(NlogN)
import java.util.Arrays; import java.util.HashMap; import java.util.Map; public class Solution { //总时间复杂度O(nlogn) public static int[] twoSum(int[] nums, int target) { int[] result = new int[2]; int len = nums.length; //(1)保存原有数组的下标索引,时间复杂度O(n) Map<Integer, Integer> indexMap = new HashMap<Integer, Integer>(); //数组中有重复的情况,如:nums=[3,3] target=6 Map<Integer, Integer> duplicateMap = new HashMap<Integer, Integer>(); for (int i = 0; i < len; i++) { if (indexMap.containsKey(nums[i])) { duplicateMap.put(nums[i], i); } else { indexMap.put(nums[i], i); } } //(2) 排序 O(nlogn) Arrays.sort(nums); //(3)一次遍历O(n) int tmp; for (int i = 0, j = len - 1; i < j; ) { tmp = nums[i] + nums[j]; if (tmp == target) { if (nums[i] == nums[j]) { result[0] = indexMap.get(nums[i]); result[1] = duplicateMap.get(nums[j]); if (result[0] > result[1]) { tmp = result[0]; result[0] = result[1]; result[1] = tmp; } } else { result[0] = indexMap.get(nums[i]); result[1] = indexMap.get(nums[j]); if (result[0] > result[1]) { tmp = result[0]; result[0] = result[1]; result[1] = tmp; } } return result; } else if (tmp > target) { j--; } else { i++; } } return null; } public static void main(String[] args) { int[] nums = new int[]{3, 3}; int target = 6; int[] result = twoSum(nums, target); System.out.println("[" + result[0] + "," + result[1] + "]"); } }
-
Tony
两次遍历:
import java.util.HashMap; import java.util.Map; public class Solution { //总时间复杂度O(n),空间复杂度O(n) public static int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); for (int i = 0; i < nums.length; i++) { map.put(nums[i], i); } 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)}; } } return null; } public static void main(String[] args) { int[] nums = new int[]{3, 3}; int target = 6; int[] result = twoSum(nums, target); System.out.println("[" + result[0] + "," + result[1] + "]"); } }
-
Tony
一次遍历:
import java.util.HashMap; import java.util.Map; public class Solution { //总时间复杂度O(n),空间复杂度O(n) public static int[] twoSum(int[] nums, int target) { Map<Integer, Integer> map = new HashMap<Integer, Integer>(); 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); } return null; } public static void main(String[] args) { int[] nums = new int[]{3, 3}; int target = 6; int[] result = twoSum(nums, target); System.out.println("[" + result[0] + "," + result[1] + "]"); } }
-