1. 两数之和
题目
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？
My Answer
public int[] twoSum(int[] nums, int target) {
int[] sub_num = new int[2];
for(int i=0; i<nums.length; i++){
for(int j=i+1; j<nums.length; j++)
if(target == nums[i] + nums[j]){
sub_num[0] = i;
sub_num[1] = j;
}
}
return sub_num;
}
官方Answer
暴力枚举
思路及算法
最容易想到的方法是枚举数组中的每一个数x，寻找数组中是否存在 target - x。
当我们使用遍历整个数组的方式寻找 target - x 时，需要注意到每一个位于 x 之前的元素都已经和 x 匹配过，因此不需要再进行匹配。而每一个元素不能被使用两次，所以我们只需要在 x 后面的元素中寻找 target - x。
public int[] twoSum(int[] nums, int target) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
for (int j = i + 1; j < n; ++j) {
if (nums[i] + nums[j] == target) {
return new int[]{i, j};
}
}
}
return new int[0];
}
复杂度分析
- 时间复杂度：O(N2)，其中 N是数组中的元素数量。最坏情况下数组中任意两个数都要被匹配一次。
- 空间复杂度：O(1)。
哈希表
思路及算法
注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。
使用哈希表，可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。
这样我们创建一个哈希表，对于每一个 x，我们首先查询哈希表中是否存在 target - x，然后将 x 插入到哈希表中，即可保证不会让 x 和自己匹配。
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<Integer, Integer>();
for (int i = 0; i < nums.length; ++i) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
复杂度分析
时间复杂度：O(N)，其中 N 是数组中的元素数量。对于每一个元素 x，我们可以 O(1) 地寻找 target - x。
空间复杂度：O(N)，其中 N 是数组中的元素数量。主要为哈希表的开销。
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-solution/
来源：力扣（LeetCode）
2. 两数相加
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的节点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
My Answer
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 逆序存储，进位加1
// 设置进位值
int increate = 0;
// 设置头node和动态node
ListNode head = new ListNode(0);
ListNode pivot = new ListNode(0);
head.next = pivot;
// 若l1或l2不为空结点，则继续计算
while(null!=l1 || null!=l2){
// 若不为空则加val，为空则加0;加上进位数
int temp = (null==l1? 0: l1.val) + (null==l2? 0: l2.val) + increate;
// 取个位和十位
int units= temp % 10;
pivot.val = units;
increate = temp / 10;
// 更新结点，避免空指针异常
if(null!=l1){
l1 = l1.next;
}
if(null!=l2){
l2 = l2.next;
}
if (null != l1 || null != l2){
pivot.next = new ListNode();
pivot = pivot.next;
}
}
// 最后进位，则新增结点
if(1 == increate){
pivot.next = new ListNode(1);
}
return head.next;
}
官方Answer
模拟
思路与算法
由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n 1 , n 2 n1,n2 n1,n2，进位值为 c a r r y carry carry，则它们的和为 n 1 + n 2 + c a r r y n1+n2+carry n1+n2+carry；其中，答案链表处相应位置的数字为* n 1 + n 2 + c a r r y n1+n2+carry n1+n2+carry* mod 10，而新的进位值为 ? n 1 + n 2 + c a r r y 10 ? ?\frac{n1+n2+carry}{10}? ?10n1+n2+carry??。
如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。
此外，如果链表遍历结束后，有$ \textit{carry} > 0$，还需要在答案链表的后面附加一个节点，节点的值为 carry \textit{carry} carry。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null;
int carry = 0;
while (l1 != null || l2 != null) {
int n1 = l1 != null ? l1.val : 0;
int n2 = l2 != null ? l2.val : 0;
int sum = n1 + n2 + carry;
if (head == null) {
head = tail = new ListNode(sum % 10);
} else {
tail.next = new ListNode(sum % 10);
tail = tail.next;
}
carry = sum / 10;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
tail.next = new ListNode(carry);
}
return head;
}
复杂度分析
-
时间复杂度： O ( max ? ( m , n ) ) O(\max(m,n)) O(max(m,n))，其中 m m m 和 n n n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O ( 1 ) O(1) O(1) 的时间。
-
空间复杂度： O ( 1 ) O(1) O(1)。注意返回值不计入空间复杂度。
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode-solution/
来源：力扣（LeetCode）