题目链接1

    1. class Solution {
    2.     public int[] twoSum(int[] nums, int target) {
    3.         HashMap<Integer,Integer> map = new HashMap<>();
    5.         for(int i =0; i < nums.length; i++) {
    6.             if(map.containsKey(target-nums[i])) {
    7.                 return new int[]{i,map.get(target-nums[i])};
    8.             }
    9.             map.put(nums[i],i);
    10.         }
    12.         return null;
    13.     }
    14. }

    题目链接2
    image.png

    1. class Solution {
    2.     public int[] twoSum(int[] numbers, int target) {
    3.         // return violence(numbers, target);
    4.         //  return binary(numbers, target);
    5.          return twoPoint(numbers, target);
    7.     }
    9.     // 1.暴力解法
    10.     public int[] violence(int[] n, int target) {
    11.         int len = n.length;
    12.         for(int i = 0; i < len-1; i++) {
    13.             for(int j = i+1; j < len; j++) {
    14.                 if((n[i]+n[j]) > target) break; // 剪枝一下，否则过不了。
    15.                 if((n[i]+n[j])==target) return new int[]{i+1,j+1};
    16.             }
    17.         }
    18.         return new int[]{0};
    19.     } 
    21.     // 2.二分法，二分的时间复杂度是logN
    22.     public int[] binary(int[] n, int target) {
    23.         int len = n.length;
    24.         for(int i = 0; i < len; i++) {
    25.             int left = i+1, right = len-1;
    26.             while (left <= right) {
    27.                 int mid = (right - left) / 2 + left;
    28.                 if (n[mid] == target - n[i]) {
    29.                     return new int[]{i + 1, mid + 1};
    30.                 } else if (n[mid] > target - n[i]) {
    31.                     right = mid - 1;
    32.                 } else {
    33.                     left = mid + 1;
    34.                 }
    35.             }
    36.         }
    38.         return new int[]{0};
    39.     }
    41.     // 3.双指针
    42.     public int[] twoPoint(int[] n, int target) {
    43.         int left = 0,right = n.length-1;
    45.         while(left < right) {
    46.             int num = n[left]+n[right];
    48.             if(num == target) {
    49.                 return new int[]{left+1, right+1};
    50.             } else if(num < target) {
    51.                 left++;
    52.             } else {
    53.                 right--;
    54.             }
    56.         }
    59.         return new int[]{-1,-1};
    60.     }
    62. }