【Leetcode】题目描述（1）
- 两数相加[1]
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 0 -> 8 原因：342 + 465 = 807
思路提供
OK，我们简单说下思路，题目意思可以简化为：给定两个非空链表，需求是将每个链表节点对应的数据域的元素相加即可，所以这是不是相当于传统的对两个整数相加的高阶版本呢，哈哈。无非注意一点就是：
- 本题是对链表的操作，即将两个链表对应节点数据加和存入另一个链表的对应节点
- 注意链表对应数据相加时的进位
以下给出C++和JavaScript两种解法，但是思路都一样，所以请读者自行选择适合自己的语言。
代码展示
- C++
class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode *dummy = new ListNode(-1), *cur = dummy; int carry = 0; while (l1 || l2) { int val1 = l1 ? l1->val : 0; int val2 = l2 ? l2->val : 0; int sum = val1 + val2 + carry; carry = sum / 10; cur->next = new ListNode(sum % 10); cur = cur->next; if (l1) l1 = l1->next; if (l2) l2 = l2->next; } if (carry) cur->next = new ListNode(1); return dummy->next; } };
- Javascript
var addTwoNumbers = function(l1, l2) { let root = {}; let carry = 0; let cursor = root; while( l1 || l2 ) { let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry; cursor.next = { val: sum % 10 } cursor = cursor.next; carry = sum>9 ? 1 : 0; l1 = l1 && l1.next; l2 = l2 && l2.next; } if ( carry > 0 ) { cursor.next = { val: carry } } return root.next; };
【Leetcode】题目描述（2）
- 两数之和[2]
给定一个整数数组nums和一个目标值 target，请你在该数组中找出和为目标值的那两个整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例：
给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1]
说下思路
01 - 整体思路概述
说下本题，题目要求可以理解成从一个数组中找出两个数使得它们的和与所给目标值相同，那很简单啊，我们可以从两个角度来考虑，每个角度又对应两种解决方法，所以一共有四种解决思路。
首先说第一个角度，从数组的层面来考虑,既然要从数组中找两个满足要求的元素，那问题就可以抽象成从数组中查找满足要求的元素的问题了，那解决方法不就出来了，无非就是查找的方法的事了呗，那笨一点，使用暴力解法，逐个遍历，好一点使用两个指针（头尾指针），根据target值与头尾指针所指数据域对应数值的大小之和来决定头尾指针的移动方向。
再说另一个角度，从所给目标值的角度考虑，我们来说一句废话：要从一个数组中找两个数字满足其相加之和等于所给目标值，是不是等价于所给目标值是否可以被拆分成两个数组元素，那思路不就来了，先说第一个思路—-组合拆分（具体讲解见下方），第二个思路有点类似于第一个思路，只不过第二个思路稍微有点局限性，即它只适用于所给目标值被拆分成两个元素的情况，即就是：用当前所给target值减去数组第一个元素（假设arr[1]<target），如果满足数组中两个元素相加之和等于target值，则除了arr[1]之外的元素肯定存在一个数组元素的值为target-arr[1]，换种说法就是target-arr[i] ，i!=1等于所存入字典中对应的key值。我们亲切的将这种方法称为我+你=全世界，ok，是不是简单了好多呢~
02 - 详述
- 暴力解法
使用两层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也没有被拆解开）
- 指针移动法
利用头尾指针，若当前头尾指针所指的指针的数据域对应的数值之和小于target值，则头指针后移，若大于target值，则尾指针前移。
代码展示
- 暴力解法
/** * 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 指针后移 } elseif (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
本文总结
在本文中，我们连续解决了Leetcode中的两道题目（两数相加[1]、两两数之和[2]），小伙伴们仅凭这几个字可能觉得这两道题目是不是重复了，相信大家在看完上述题解之后，是不是都明白了呢？快去实现一下吧~
