image-20220319131035278.png

我仍记得第一题哈希表的小震惊..

划重点，有序，所以二分是可行的

二分

  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         for (int i = 0; i < numbers.length; ++i) {
  4.             int low = i + 1, high = numbers.length - 1;
  5.             while (low <= high) {
  6.                 int mid = (high - low) / 2 + low;
  7.                 if (numbers[mid] == target - numbers[i]) {
  8.                     return new int[]{i + 1, mid + 1};
  9.                 } else if (numbers[mid] > target - numbers[i]) {
  10.                     high = mid - 1;
  11.                 } else {
  12.                     low = mid + 1;
  13.                 }
  14.             }
  15.         }
  16.         return new int[]{0};
  17.     }
  18. }

双指针

两个指针分别指向第一个元素位置和最后一个元素的位置。每次计算两个指针指向的两个元素之和，并和目标值比较。如果两个元素之和等于目标值，则发现了唯一解。如果两个元素之和小于目标值，则将左侧指针右移一位

  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         int low = 0, high = numbers.length - 1;
  4.         while (low < high) {
  5.             int sum = numbers[low] + numbers[high];
  6.             if (sum == target) {
  7.                 return new int[]{low + 1, high + 1};
  8.             } else if (sum < target) {
  9.                 ++low;
  10.             } else {
  11.                 --high;
  12.             }
  13.         }
  14.         return new int[]{0};
  15.     }
  16. }

还行溜了溜了