classSolution{ publicint[] twoSum(int[] numbers, int target) { int[] ans = newint[2]; int len = numbers.length; for (int i = 0; i < len - 1; i++) { int need = target - numbers[i]; for (int j = i + 1; j < len; j++) { if (numbers[j] == need) { ans[0] = i + 1; ans[1] = j + 1; return ans; } } } return ans; } }
双指针
时间复杂度:O(n)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
classSolution{ publicint[] twoSum(int[] numbers, int target) { int left = 0, right = numbers.length - 1, mid; while(left < right){ mid = numbers[left] + numbers[right]; if(mid == target) returnnewint[] {left + 1, right + 1}; elseif(mid < target) left ++; else right --; } returnnull; } }
二分查找
时间复杂度:O(nlogn)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution{ publicint[] twoSum(int[] num, int target) { for (int i = 0; i < num.length; i++) { int low = i + 1, high = num.length - 1; int val = target - num[i]; while (low <= high) { int mid = low + (high - low) / 2; //用>>会超时。。。 if (num[mid] == val) returnnewint[]{i + 1, mid + 1}; elseif (num[mid] < val) low = mid + 1; else high = mid - 1; } } returnnull; } }
classSolution{ publicint[] twoSum(int[] num, int target) { Map<Integer, Integer> map = new HashMap<>(num.length); for (int i = 0; i < num.length; i++) { if (map.get(target - num[i]) != null) { returnnewint[]{map.get(target - num[i]) + 1, i + 1}; } map.put(num[i], i); } returnnull; } } /* 或者 public int[] twoSum(int[] numbers, int target) { int[] ans = new int[2]; int len = numbers.length; Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < len; i++) { map.put(numbers[i], i + 1); } for (int i = 0; i < len; i++) { int need = target - numbers[i]; if (map.containsKey(need)) { ans[0] = i + 1; ans[1] = map.get(need); return ans; } } return ans; } */