1、地址

https://leetcode-cn.com/problems/two-sum/

2、题面分析

题目

image.png

题目信息

  • 1、如果多重解出现，返回一个就行
  • 2、每个数组中的整数，最多被使用一次。【返回的下表，必须是不同的】

  • 3、下标返回可以无序

    3、暴力求解法—O(1、两数之和 - 图3)

    求解思路

    顺序选取
    依次枚举出所有组合，当某种组合对应的两数之和等于target返回解

  • 设定两个指针i，j永远可以假设 i < j

  • 初始化时，则需要使 j = i + 1

    代码实现

    1. class Solution {
    2.   public int[] twoSum(int[] nums, int target) {
    3.       int[] ret = new int[2];
    4.       int len = nums.length;
    5.       for(int i = 0 ; i < len - 1; i++){
    6.           for(int j = i + 1 ; j < len; j++ ){
    7.               if(nums[i] + nums[j] == target){
    8.                   ret[0] = i;
    9.                   ret[1] = j;
    10.                   return ret;
    11.               }
    12.           }
    13.       }
    14.       return ret;
    15.   }
    16. }

    总结

    如果求解的问题是输入的一个子集，那么可以尝试暴力枚举

4、二分查找

求解思路

找到一个时间复杂度小于 O(1、两数之和 - 图4) 的算法

  • 暴力破解的内循环，变成二分查找

代码实现

  1. class Solution {
  2.     public int[] twoSum(int[] nums, int target) {
  3.         int[] ret = new int[2];
  4.         int len = nums.length;
  5.         int[] sortedNums = nums.clone();
  6.         Arrays.sort(sortedNums);
  7.         for(int i = 0 ; i < len ; i++){
  8.             int cur = sortedNums[i];
  9.             int findTarget = target - cur;
  10.             int index = binarySearchInSortedArray(sortedNums, findTarget, i + 1);
  11.             if(index != -1){
  12.                 return remapping(nums, sortedNums[i], sortedNums[index]);
  13.             }
  14.         }
  15.         return ret;
  16.     }
  18.     public int[] remapping(int[] nums, int t1, int t2){
  19.         int i = -1, j = -1;
  20.         for(int index = 0; index < nums.length; index ++ ){
  21.             if(i == -1 && t1 == nums[index]){
  22.                 i = index;
  23.             }
  25.             if(t2 == nums[index]){
  26.                 j = index;
  27.             }
  28.             if(i != -1 && j != -1 && i != j){
  29.                 break;
  30.             }
  31.         }
  33.         return new int[] {i, j};
  34.     }
  36.     public int binarySearchInSortedArray(int[] sortedNums, int target, int startIndex){
  37.         int leftIndex = startIndex;
  38.         int rightIndex = sortedNums.length - 1;
  39.         while(leftIndex <= rightIndex){
  40.             int midIndex = leftIndex + (rightIndex - leftIndex) / 2;
  41.             int mid = sortedNums[midIndex];
  42.             if(target == mid){
  43.                 return midIndex;
  44.             }
  45.             if(target < mid){
  46.                 rightIndex = midIndex - 1;   
  47.             }else{
  48.                 leftIndex = midIndex + 1;
  49.             }
  50.         }
  51.         return -1;
  52.     }
  53. }

5、Hash表求解

求解思路

代码实现

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