给定一个数组，一个目标值，请在数组中找到和为目标值的两个数字，并返回他们的数组下标。 你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

eg.给定 nums = [2, 7, 11, 15], target = 13，因为 nums[0] + nums[2] = 2 + 11= 13，所以返回 [0, 2]
----------------------------------------------分割线----------------------------------------------------------------------

• 解法一：

  暴力解法，两层循环，一次取出元素进行相加对比，空间复杂度O(1) ,时间复杂度O(n^2)

  class Solution{
    public int[] sum(int[] nums,int target){
        for(int i = 0 ;i<nums.length;i++){
           for(int j = i+1;j<nums.length;j++){
               if(nums[i] + num[j] == target){
                   return new Int[]{i,j};
               }
           }
        }
        throw new IllegalArgumentException("未找到")；
    }
  }
  

• 解法二：

  借助哈希表，第一次迭代将元素，以及元素对应下标存入哈希表，然后第二次迭代，依次取出数组元素，计算该元素与目标值的差值，查看该差值是否存在于哈希表中，如果存在，并且下表不是本次元素，则返回该值和差值对应下标。

  空间复杂度O(n),时间复杂度O(n)

  class Solution {
       public int[] twoSum(int[] nums, int target) {
           Map<Integer, Integer> hashMap = new HashMap();
           for(int i = 0; i < nums.length; i++){
               hashMap.put(nums[i], i);
          }
           for(int i = 0; i < nums.length; i++){
              int num = target - nums[i];
                if(hashMap.containsKey(num) && hashMap.get(num) != i){
                 return new int[] {i, hashMap.get(num)}            
                }
          }
          throw new IllegalArgumentException("未找到");    
       }
  }
  

  • 解法二优化：

  只用一次迭代，先计算差值，然后去哈希表中查询，如果找到，返回结果，如果未找到，该元素存入哈希表。

  class Solution {
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> hashMap = new HashMap();
            for(int i = 0; i < nums.length; i++){
                int num = target - nums[i];
               if(hashMap.containsKey(num)){
                   return new int[] {i, hashMap.get(num)};
                }
                hashMap.put(nums[i], i);
           }
           throw new IllegalArgumentException("未找到");
       }
  }
  

  class Solution{//for kotlin
      fun sum(nums:IntArray,target:Int):IntArray{
          val hashMap:HashMap<Int,Int> = HashMap()
          for((index,e) in nums.withIndex()){
              val num:Int = target - e
              if(hashMap.containsKey(num)){
                  return intArrayOf(hashMap[num]!!,index)
              }
               hashMap.put(e,index)
          }
         throw IllegalArgumentException("未找到")
      }
      
  }
  

  class Solution{// for dart
    List sum(List nums,int target){
      Map map = Map();
      for(int i = 0;i<nums.length;i++){
        int num = target - nums[i];
        if(map.containsKey(num)){
          return [map[num],i];
        }
        map.addAll({nums[i]:i});
      }
      throw Exception("未找到");
    }
  }
  

  • 变种----给定数组为升序有序数组

  class Solution {
      //因为数组是有序的，那么两个指针，一个在头一个在尾，一层循环就能保证结果正确
      public int[] twoSum(int[] numbers, int target) {
          int start=0;
          int end=numbers.length-1;
          int result[]=new int[2];
          while (start<end){
              int temp=numbers[start]+numbers[end];
              if(temp==target) {
                  result[0]=start+1;
                  result[1]=end+1;
                  return result;
              }else if(temp<target){
                  int t=numbers[start];
                  start++;
                  while (numbers[start]==t){//去除与start相等的值来进行比较
                      start++;
                  }
              }else {
                  int t=numbers[end];
                  end--;
                  while (numbers[end]==t){
                      end--;
                  }
              }
          }
          return result;
      }
  }