2019-05-14 | 算法 | UNLOCK

两数之和

题目描述

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

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

说下思路

整体思路概述
说下本题,题目要求可以理解成从一个数组中找出两个数使得它们的和与所给目标值相同,那很简单啊,我们可以从两个角度来考虑,每个角度又对应两种解决方法,所以一共有四种解决思路.

  • 首先说第一个角度,从数组的层面来考虑,既然要从数组中找两个满足要求的元素,那问题就可以抽象成从数组中查找满足要求的元素的问题了,那解决方法不就出来了,无非就是查找的方法的事了呗,那笨一点,使用暴力解法,逐个遍历,好一点使用两个指针(头尾指针),根据target值与头尾指针所指数据域对应数值的大小之和来决定头尾指针的移动方向.

  • 再说另一个角度,从所给目标值的角度考虑,我们来说一句废话:要从一个数组中找两个数字满足其相加之和等于所给目标值,是不是等价于所给目标值是否可以被拆分成两个数组元素,那思路不就来了,先说第一个思路—-组合拆分(具体讲解见下方),第二个思路有点类似于第一个思路,只不过第二个思路稍微有点局限性,即它只适用于所给目标值被拆分成两个元素的情况,即就是 : 用当前所给target值减去数组第一个元素(假设arr[1]<target),如果满足数组中两个元素相加之和等于target值,则除了arr[1]之外的元素肯定存在一个数组元素的值为target-arr[1],换种说法就是target-arr[i] ,i!=1等于所存入字典中对应的key值.,我们亲切的将这种方法称为我+你=全世界,ok,是不是简单了好多呢~

详细讲讲

  • 暴力解法
    使用两层for循环,对数组元素进行遍历,当且仅当数组中的两个元素之和等于目标值时,申请一段内存空间,并记录此时对应数组元素的下标.
    【注】: malloc函数
    函数声明 : void malloc(int size);
    说明:malloc 向系统申请分配指定size个字节的内存空间。返回类型是 void
    类型。void 表示未确定类型的指针。C,C++规定,void 类型可以强制转换为任何其它类型的指针。如果分配成功则返回指向被分配内存的指针,否则返回空指针NULL。

  • 组合拆分
    还记得上一篇博客(就是罗马数字与整数的相互转换那篇),我们提到了组合拆分的方法,即对于一个从大到小排序的数组,用目标值与数组元素逐一开始比较,当且仅当目标值大于或等于某一项数组元素时,此时用目标值减去当前数组元素(target-nums[i]),然后用余数继续与当前数组元素的下一个数组元素进行比较,同样找出余数大于或等于数组元素的那一项,重复此操作,直至target被完全拆解或者数组元素遍历完成之后target也没有被拆解为止.

举个栗子 :

给定数组[11,8,6,2,1]
给定目标值target=12
则:判断12与所有数组元素的大小关系,因为12>11且12-11=1,用余数继续与后面的元素进行比较,直至余数大于或等于数组元素时(还有一种状况就是数组元素被遍历完成了,target也没有被拆解开/(ㄒoㄒ)/~~)
  • 指针移动法
    利用头尾指针,若当前头尾指针所指的指针的数据域对应的数值之和小于target值,则头指针后移,若大于target值,则尾指针前移.

talk is cheap,show you my code

  • 暴力解法
    /**
    * Note: The returned array must be malloced, assume caller calls free().
    */
    int* twoSum(int* nums, int numsSize, int target) {
      int i = 0, j = 0;
      int n = numsSize;
      int* result = NULL;
      for(i = 0; i < n; i++) {
          for(j = i + 1; j < n; j++) {
              if(target == nums[i] + nums[j]) {
                  result = (int*)malloc(sizeof(int) * 2);
                  result[0] = i;
                  result[1] = j;
                  return result;
              }
          }
      }
      return result;
    }
    
  • 指针移动法

    class Solution {
    public:
    vector<int> twoSum(vector<int>& nums, int target) {
        struct Node {
            // 保存数组中每个数的值和排序前所在下标
            int index, val;
            bool operator <(Node &n) {
                return val < n.val;
            }
        };
    
        vector<int> res;
        int size = nums.size();
        Node nodes[size];
        for (int i = 0; i < size; i++) {
            nodes[i].val = nums[i], nodes[i].index = i;
        }
        sort(nodes, nodes + size);
        int start = 0, end = size - 1, t;
        while (start < end) {
            t = nodes[start].val + nodes[end].val;
            // 等于
            if (t == target) {
                res.push_back(nodes[start].index);
                res.push_back(nodes[end].index);
                return res;
            // 小于, start 指针后移
            } else if (t < target) {
                start++;
            // 大于,end 指针前移
            } else {
                end--;
            }
        }
        return res;
    }
    };
    
  • 我+你=全世界
    class Solution:
      def twoSum(self,nums, target):
          n = len(nums)
          d = {}
          for x in range(n):
              a = target - nums[x]
              if nums[x] in d:
                  return d[nums[x]],x
              else:
                  d[a] = x
    

评论加载中