給定一個(gè)數(shù)組，一個(gè)目標(biāo)值，請?jiān)跀?shù)組中找到和為目標(biāo)值的兩個(gè)數(shù)字，并返回他們的數(shù)組下標(biāo)。 你可以假設(shè)每種輸入只會對應(yīng)一個(gè)答案。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素。

eg.給定 nums = [2, 7, 11, 15], target = 13，因?yàn)?nums[0] + nums[2] = 2 + 11= 13，所以返回 [0, 2]
----------------------------------------------分割線----------------------------------------------------------------------

• 解法一：

  暴力解法，兩層循環(huán)，一次取出元素進(jìn)行相加對比，空間復(fù)雜度O(1) ,時(shí)間復(fù)雜度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("未找到")；
    }
  }
  

• 解法二：

  借助哈希表，第一次迭代將元素，以及元素對應(yīng)下標(biāo)存入哈希表，然后第二次迭代，依次取出數(shù)組元素，計(jì)算該元素與目標(biāo)值的差值，查看該差值是否存在于哈希表中，如果存在，并且下表不是本次元素，則返回該值和差值對應(yīng)下標(biāo)。

  空間復(fù)雜度O(n),時(shí)間復(fù)雜度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("未找到");    
       }
  }
  

  • 解法二優(yōu)化：

  只用一次迭代，先計(jì)算差值，然后去哈希表中查詢，如果找到，返回結(jié)果，如果未找到，該元素存入哈希表。

  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("未找到");
    }
  }
  

  • 變種----給定數(shù)組為升序有序數(shù)組

  class Solution {
      //因?yàn)閿?shù)組是有序的，那么兩個(gè)指針，一個(gè)在頭一個(gè)在尾，一層循環(huán)就能保證結(jié)果正確
      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相等的值來進(jìn)行比較
                      start++;
                  }
              }else {
                  int t=numbers[end];
                  end--;
                  while (numbers[end]==t){
                      end--;
                  }
              }
          }
          return result;
      }
  }