image.png

    1. public class Test {
    2.     public static void main(String[] args) {
    3.         System.out.println(Arrays.toString(twoSeach(new int[]{1,2,3,4,5,6},10)));
    4.         System.out.println(Arrays.toString(twoPoint(new int[]{1,2,3,4,5,6},10)));
    5.     }
    7.     /**
    8.      * 双指针，时间复杂度O(n)，空间复杂度O(1)
    9.      * @param arr
    10.      * @param target
    11.      * @return
    12.      */
    13.     private static int[] twoPoint(int[] arr, int target) {
    14.         int left = 0, right = arr.length - 1;
    16.         while (left < right) {
    17.             if (arr[left] + arr[right] == target) {
    18.                 return new int[]{left, right};
    19.             } else if (arr[left] + arr[right] > target){
    20.                 right--;
    21.             } else {
    22.                 left++;
    23.             }
    24.         }
    26.         return new int[]{0};
    27.     }
    29.     /**
    30.      * 二分查找
    31.      * @param arr
    32.      * @param target
    33.      * @return
    34.      */
    35.     private static int[] twoSeach(int[] arr, int target) {
    36.         // 二分查找法，先循环固定一个值
    37.         for (int i = 0; i < arr.length; i++) {
    38.             // 起始指针每次循环+1
    39.             int start = i,end = arr.length - 1;
    40.             while (start <= end) {
    41.                 int middle = start + (end - start)/2;
    42.                 if (arr[middle] == target - arr[i]) {
    43.                     return new int[]{i, middle};
    44.                 } else if (arr[middle] > target - arr[i]){
    45.                     end = middle - 1;
    46.                 } else {
    47.                     start = middle + 1;
    48.                 }
    49.             }
    50.         }
    51.         return new int[]{0};
    52.     }
    54. }